[시뮬레이션] 압축 - 2018 KAKAO BLIND RECRUITMENT

해결방법

i) map을 이용하여 길이가 1인 모든 단어를 포함하는 사전을 초기화한다. map은 <string, int> 쌍으로 만들면 된다.

ii) map에서 현재 입력과 일치하는 가장 긴 문자열을 찾는다.

iii) 가장 긴 문자열에 해당하는 사전의 색인 번호를 출력한다.

iv) 가장 긴 문자열의 뒤에 문자가 남아있을 경우, 가장 긴 문자열에서 그 문자를 덧붙이고 map에 넣는다.

v) 현재 위치를 그 문자의 위치로 이동한다.

 

 

소스코드

#include <string>
#include <vector>
#include <map>
using namespace std;

map<string, int> dic;

vector<int> solution(string msg) {
    vector<int> answer;
    for(int i=0;i<26;i++){
        string s="";
        s+=(char)('A'+i);
        dic[s]=i+1;
    }
    string longest, tmp;
    for(int i=0;i<msg.length();i++){
        longest="";
        for(int j=i;j<msg.length();j++){
            tmp=msg.substr(i, j-i+1);
            if(dic.count(tmp)) longest=tmp;
            else break;
        }
        answer.push_back(dic[longest]);
        if(i+longest.length()<msg.length()) dic[msg.substr(i, longest.length()+1)]=dic.size()+1;
        i+=longest.length()-1;
    }
    return answer;
}

 

테스트케이스 20개 모두 정답

 

 

출처 : https://programmers.co.kr/learn/courses/30/lessons/17684