[프로그래머스] 압축 (C++)

프로그래머스 압축

1. 문제

문제 링크

2. 접근법

[ 문제 풀이 ]

 

위 문제는 2018 카카오 코딩 테스트에 출제된 문제이다.

 

1. 알파벳 대문자를 map을 사용하여 문자와 인덱스를 넣어준다.

2. 단어를 나누는 위치와 현재 단어 개수를 초기화해준다.

3. while문으로 단어를 압축한다.

4. 반복자를 사용하여 해당 단어가 사전에 존재하는지 여부를 파악한다.

5. 만약 w가 사전에 있다면 answer에 인덱스를 넣어주고,

6. wc 반복자를 이용하여 wc가 존재한다면 cnt를 계속 늘려주고, 존재하지 않는다면 맵에 wc 문자와 인덱스를 담아준다.

7. 그리고 msg에서 wc를 지우고 cnt를 1로 바꿔준다.

8. 다음 문자 c가 msg의 끝에 도달하면 answer에 마지막 인덱스를 넣어주고 while문을 바로 종료시킨다.

3. 코드

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

vector<int> solution(string msg) {
    vector<int> answer;
    vector<string> alpha = { "A", "B","C","D", "E","F","G", "H","I"
        ,"J","K","L", "M","N","O","P","Q", "R","S","T","U",
        "V", "W","X","Y","Z" };
    int cnt = 1, currNum = 27;
    map<string, int> word;
    //맵에 알파벳과 인덱스 값 넣어주기
    for (int i = 0; i < 26; ++i)
    {
        word.insert(make_pair(alpha[i], i + 1));
    }
    while (1)
    {
        string w = msg.substr(0, cnt);
        string c = msg.substr(cnt, 1);
        string wc = w + c;
        auto tmp_w = word.find(w);
        auto tmp_c = word.find(c);
        auto tmp_wc = word.find(wc);
        //맵에 w가 존재한다면
        if (tmp_w != word.end())
        {
            //맵에 wc가 존재한다면 cnt++
            if (tmp_wc != word.end())
            {
                if (cnt < msg.size())
                    cnt++;
            }
            //wc가 존재하지 않는다면 answer에 w인덱스 담고 맵에 wc넣기
            else
            {
                answer.push_back(tmp_w->second);
                word.insert(make_pair(wc, currNum++));
                msg.erase(0, cnt);
                cnt = 1;
            }

        }
        //다음 문자가 msg의 끝에 도달하면 이전 인덱스를 answer에 담고 바로 종료
        if (c == "\0")
        {
            answer.push_back(tmp_w->second);
            break;
        }
    }
    return answer;
}

4. 결과