카카오 신입 공채 3차 코딩 테스트 풀이 - 2번문제

3차테스트 2번은 압축 알고리즘을 제한된 환경에서 주어진 규칙대로 구현하는 문제입니다. (문제는 위의 출처에서 읽고 오시는 것을 추천드립니다.) 여기서 먼저 알아야 될 것은 어떤 상황에 문자열이 사전에 추가되는지입니다. 하지만 다소 쉬운 규칙을 사용하고 있는 것을 확인할 수 있습니다.

우리는 압축을 할 때사전에 있는 단어 중 가장 긴 단어로 색인을 하고, 그 다음 글자를 붙여 인덱스를 증가시키므로 이를 그대로 진행하면 문제가 풀릴 것을 알 수 있습니다. 문제의 제한범위상 1000글자 이하의 글자가 인풋으로 주어지므로, 가장 긴 문자열이 모두 새롭게 사전에 들어간다 하더라도 $(1000*1001)/2 = 500,500$ 글자를 넘지 않습니다. 1번 문제와 동일하게 그냥 풀면 됩니다. 프로그램의 수행 속도를 빠르게 하기 위해 해쉬 구조의 자료구조를 이용하는 점도 중요합니다.

vector<int> solve(string msg)
{
    string alp = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    vector<int> ans;
    map<string,int> dictionary;
    for (int i = 0; i < 26; i++) {
        dictionary[alp.substr(i,1)] = i + 1;
    }
    for (int i = 0; i < msg.length();)
    {
        string chk = "";
        while (i<msg.length() && dictionary.find(chk + msg[i]) != dictionary.end()) {
            chk += msg[i++];
        }
        ans.push_back(dictionary[chk]);
        if (i < msg.length()) {
            dictionary[chk + msg[i]] = dictionary.size() + 1;
        }
    }
    return ans;
}