2018 KAKAO BLIND RECRUITMENT [3차] 압축, C++

문제는 간단하다. 아래 지문을 그대로 구현만 하면 된다.

LZW 압축은 다음 과정을 거친다.

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.

단순히 쉽지만, C++ String을 쓰면서 깨달았던 점을 정리하기 위해 글을 작성한다.

1. Char to String

String으로 변환할 때 단순하게 암묵적 변환을 쓰면 해당 글자에 해당하는 아스키 코드의  숫자가 들어간다. 그리고 명시적으로 변환한다고 한들 제대로 되지 않으니, String 변수를 하나 선언해야 한다.

string s = ""; s += c; 와 같이 해도 되나 길어서 별로니 아래처럼 하면 된다.
string(1, c); 

2. 문자열을 찾을 때에는 문자열을 잘라 사용하기

찾는 위치를 정해주지 않기 때문에 편리하다.

 

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

vector<int> solution(string msg) {
    vector<int> answer;    
    map<string, int> m;
    
    for(int i=0; i<26; i++) {
        m.insert({std::string(1, 'A' + i), i+1});
    }
    
    bool check = true;
    int w = 0;
        
    while(msg.size() > 0) {
        int index = 0;
        string temp = msg.substr(w, 1);
        int i = msg.size();
        for(; i>0; i--) {
            temp = msg.substr(w, i);
            if(m.find(temp) != m.end()) {
                index = m[temp];
                break;
            }
        }
        temp = msg.substr(w, i+1);
        m.insert({temp, m.size()+1});
        answer.push_back(index);
        msg = msg.substr(i);
    }  
        
    return answer;
}