[프로그래머스 LV 2] [3차] 압축

 

초기생각

문제의 설명을 읽어보면 A가 1이고 Z가 26이라 Map을 사용하여 1부터 26까지 사전으로 등록해주는게 좋을 것 같다고 생각하였다. 

그리고 LZW압축 과정이 처음에는 이해가 잘 되지않았는데 천천히 읽어보니  문자열에서 사전에 등록돼있는 것 중 가장  긴 문자열을 찾은 후 그 문자열에 맞는 사전에서의 번호를 answer에 추가하고 사전에 없는 단어를 추가해주면 되는 것이었다.

근데 이렇게 생각하니 사전에 등록돼있는 것 중 가장 긴 문자열을 어떻게 찾아야하나 고민을 하다가 사전에 등록되어 있는 것을 찾을 생각보다 사전에 등록되어 있지않은 걸 찾으면 그 전에까지는 등록된 것이니 그 부분만 잘라서 쓰면 되겠다라는 해답이 나왔다.

 

● 사전에 등록하는 부분에서는 num이라는 전역변수를 사용하여 뒤에 수도 추가될 수 있게 하였다.

알고리즘은 생각하면서 하나의 방법도 좋지만 여러 방법을 생각해보는게 좋을 것 같다.

#include <string>
#include <vector>
#include <map>
using namespace std;
map<string, int> dic;
int num = 1;
vector<int> solution(string msg) {
    vector<int> answer;
    //A ~ Z 까지 사전에 등록
    for (char c = 'A'; c <= 'Z'; c++) {
        string s = "";
        s += c;
        dic[s] = num++;
    }
    //사전추가 과정
    string sum="";
    for(int i=0;i<msg.length();i++){
        sum+=msg[i];
        if(dic[sum]==0){            //만약 사전에 등록되지않은 단어라면
            dic[sum]=num++;             
            sum=sum.substr(0,sum.length()-1);           //사전에 등록되지않은거 바로 앞에까지는 등록된 단어
            answer.push_back(dic[sum]);                 //등록된 단어의 번호 push_back
            sum="";                                     //단어 초기화
            i--;                                        //사전에 등록되지 않은 수의 인덱스에서 시작 
        }
    }
    answer.push_back(dic[sum]);             //마지막 단어
    
    return answer;
}