코딩 공부 - 프로그래머스 - [3차] 압축

문제

• [3차] 압축

설명

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

코드

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

using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;             // 문자열을 압축한 후의 사전 색인 번호 배열
    map<string, long long> dict;    // 단어 사전
    stringstream ss;                // 스트링버퍼
    long long counter = 0;          // 색인번호 카운터
    
    // 길이가 1인 모든 단어를 포함하도록 사전 초기화
    for (char i = 'A'; i <='Z'; i++) {
        ss << i;
        dict.insert(make_pair(ss.str(), ++counter));
        ss.str("");
    }
    int right = 0;
    int left = 0;
    int num = 0;
    // 문자열 압축
    for (;;) {
        // 시작 인덱스가 문자열 범위를 벗어난경우
        if (left > msg.size()) {
            ss.str("");
            ss << msg[msg.size()-1];
            auto tt = dict.find(ss.str());
            if (tt == dict.end()) {
                answer.push_back(++counter);
            } else {
                answer.push_back(tt->second);
            }
            break;
        }
        // 마지막 문자인 경우
        if (right > msg.size() - 1) {
            ss.str("");
            ss.str(msg.substr(left, msg.size() - left));
            auto tt = dict.find(ss.str());
            if (tt == dict.end()) {
                answer.push_back(++counter);
            } else {
                answer.push_back(tt->second);
            }
            break;
        }
        
        ss << msg.at(right);
        auto found = dict.find(ss.str());
        if (found != dict.end()) {
            // 사전에 이미 추가된 경우
            right++;
            num = found->second;
        } else {
            // 사전에 없는 경우
            // 사전에 새로운 단어 추가,
            // 이전에 검색된 단어의 색인번호 저장
            answer.push_back(num);
            left = right;
            dict.insert({ss.str(), ++counter});
            num = 0;
            ss.str("");
        }
    }
    
    return answer;
}