[3차]압축

들어가는 말

LZW에 관한 문제다. 첫 문자(w)부터 검사를 하는데, 만일 다음 글자(c)와 합한 값이 존재하지 않는다면 합한 값(w+c)을 사전에 넣고 다음 글자를 제거한 첫 문자(w)만을 출력하면 되는 것이다. 허프만 압축과 함께 학교에서 배웠던 적이 있어 문제 이해는 어렵지 않았다. 구현이 문제였지...

코드 설명

일단 string형 벡터에다가 A~F를 저장해줬다. 어제 풀었던 n진수 게임 풀이와 마찬가지로. 문자열을 나누고 인덱스를 부여하는 게 문제였는데 찾아보니까 다들 map함수로 풀었더라. Map 함수는 key와 value로 이루어진 tree라고 할 수 있다. 특히 key는 중복이 불가능하다. Map함수에 관해서는 나중에 설명하도록 하고 미리 정의해둔 v를 map에 넣어준다(map의 key는 string로 value는 int로 정의했다).
전부 넣어줬다면 이제는 문자열 끝까지 돌면서 압축을 할 차례다. tmp는 현재 문자(w)에 다음 문자(c)를 합한 값이다(tmp = tmp + msg[i];). 만약 tmp값을 w에서 찾았는데 찾지 못했다면(if(w.find(tmp) == w.end())) tmp의 값을 map에 넣으주면 된다(w[tmp] = count++;). 그리고 w의 값만을 tmp에 저장한 다음에 answer에 w[tmp]의 value를 넣어주고 tmp는 초기화 i는 하나 빼주면 된다. 여기서 tmp.length()-1을 해주는 이유는 만약에 wc가 없다면 w만을 넣어줘야 돼서 그렇다. 그리고 c에서부터 다시 검사를 해줘야 하니 i--하는 것이고.
w.find(tmp) == w.end()는 w[tmp] == 0으로 쓸 수 있다. 둘다 tmp의 값이 map로 정의한 w에 없다는 의미다.

코드

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

using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    vector<string> v = {"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"};
    map<string, int> w;
    int count = 27;
    string tmp = "";

    for(int i=0; i<26; i++){
        w.insert(make_pair(v[i], i+1));
    }
        
    for(int i=0; i<msg.length(); i++){
        tmp = tmp + msg[i];
        if(w.find(tmp) == w.end()){
            w[tmp] = count++;
            tmp = tmp.substr(0, tmp.length()-1);
            answer.push_back(w[tmp]);
            tmp = "";
            i--;
        }
    }
    answer.push_back(w[tmp]);
    

    return answer;
}

참고

https://yabmoons.tistory.com/675
https://eunchanee.tistory.com/80