[C++] 프로그래머스 [3차] 압축

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

프로그래머스

풀이

주어진 문자열 msg를 압축하는데 주어진 조건

1. 사전에 존재하는 가장 긴 문자열 w 찾기
2. w 색인 번호를 answer에 넣고 w를 msg에서 제거하기
3. 입력에서 처리되지 않은 다음 글자 c가 존재한다면 w+c에 해당하는 단어를 사전에 등록

해야 하는 문제입니다.

 

unordered_map 자료구조(dict 변수)를 사용해 알파벳 순으로 먼저 사전을 초기화해주었습니다.

다음 for 문과 while 문에서는 사전에 존재하는 가장 긴 문자열 w (str_w 변수) 를 찾습니다. 이때 사전 dict 에 존재하지 않는다면 새로 등록해야 하는 w+c에 해당합니다. 

따라서, w+c를 먼저 사전에 등록해주고 substr()을 사용해 바로 직전 문자에 해당하는 색인을 answer에 추가합니다. 

2번 조건은 i += str_w.size()를 사용해 w에 해당하는 길이만큼 건너띄어 줍니다.

 

마지막 문자에 도달 후 다음은 공백 문자를 추가하므로 if 문에 들어가서 문제없이 정답을 추가한 후 for 문이 종료됩니다.

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

unordered_map<string, int> dict;
string s[] = {"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"};

vector<int> solution(string msg) {
    vector<int> answer;
    int num_cnt = 26;
    for (int i = 0; i < num_cnt; i++) {
        dict[s[i]] = i+1;
    }
    string str_w;

    for (int i = 0; i < msg.size(); ) {
        // w 찾기
        int j = i;
        while (true) {
            str_w += msg[j];
            if (dict[str_w] == 0) {
                // 사전에 없는 경우
                dict[str_w] = ++num_cnt; // w+c 등록
                str_w = str_w.substr(0, j-i);
                answer.push_back(dict[str_w]); // 출력
                i += str_w.size();
                str_w = ""; // 초기화
                break;
            }
            j++;
        }
    }
    return answer;
}