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


작성일 : 2018-06-04 23:36:50
조회수 : 1026



본문

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;

}

카카오 신입 공채 3차 코딩 테스트 풀이 - 2번문제 - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.