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

 이 문제는 맵을 이용한 구현 문제이다. 문제에 주어진 설명 그대로 구현하면 바로 시간 초과 없이 정답이 나온다. 왜냐하면 msg에 대해 루프를 돌리는데 사전에 없는 단어가 나올때의 그 문자부터 시작하므로 결국 O(N) 시간이 걸리고, msg의 최대 길이가 1,000 밖에 되지 않기 때문이다.

 

 

 이 문제를 풀기 위해 다음과 같은 수도 코드를 작성하였다.

temp += msg[index]
		
만약 dic[temp] == 0이라면	// 사전에 없음
	answer에 dic[prev] 추가
	dic[temp] = pushIndex
	pushIndex++
	index--
	temp = ""
	prev = ""
	
0이 아니라면 // 사전에 있음
	prev = temp;
	continue

index++

 처음에는 while문 안에 for문이 있어 그 안에 저 수도코드가 동작하도록 구현했지만, 생각해보니 굳이 그럴 필요가 없었고 애초에 정답도 안 나온다. 단일 반복문만으로 충분히 해결 가능한 로직이었다.

 

 

 한 가지 유의할 점은 루프가 끝나고 나면 마지막 문자열이 temp에 남아있게 되는데, 남아있는 문자열은 반드시 사전에 존재하는 단어이다. KAKAO 를 예시로 들었을 때, KAKA 까지 수행하고 O를 검사하게 되는데, 이는 단일 문자이므로 반드시 사전에 존재한다. 또한 TOBEORNOTTOBEORTOBEORNOT 를 예시로 들어도, 마지막에 OT 가 남게 되는데 이는 첫번째 분기문에서 걸리지 않았기 때문에 이렇게 유지되는 것이다. 따라서 반드시 남아있는 문자열은 사전에 존재하는 단어가 되므로 answer에 push 해주면 정답이 나오게 된다.

 

 

 

 

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    
    map<string, int> dictionary;
    
    for (int i = 1; i <= 26; i++) {
        string temp = "";
        temp += 'A' + (i - 1);
        dictionary[temp] = i;
    }
    
    // base case
    if (msg.size() == 1) {
        string temp = "";
        temp += msg[0];
        
        answer.push_back(dictionary[temp]);
        
        return answer;
    }
    
    int pushIndex = 27;
    int index = 0;
    
    string temp = "";
    string prev = "";
    
    while (index < msg.size()) {
        temp += msg[index];
            
        if (dictionary[temp] == 0) {
            answer.push_back(dictionary[prev]);
            dictionary[temp] = pushIndex;
            pushIndex++;
            temp = "";
            prev = "";
            index--;
        }
        else {
            prev = temp;
        }
        index++;
    }
    
    answer.push_back(dictionary[temp]);
    
    return answer;
}