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

 

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/17684

프로그래머스

---

 

해결전략

 

문자열

Map

검색

 LZW(Lempel–Ziv–Welch) 압축 알고리즘

 

---

 

정답 코드

 

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

map<string, int> myMap; // 사전 등록에 쓰일 map

vector<int> solution(string msg) {
    vector<int> answer;

    for (int i = 0; i < 26; i++) { // A~Z 등록
        string alphabet(1, 'A' + i);
        myMap[alphabet] = i + 1;
    }

    int x = 27; // 알파벳 26개 다음부터 등록하게 되니 27부터 시작
    for (int i = 0; i < msg.size();) // 주의! i++이 아니라 밑의 i += temp.size();사용
    {
        string temp(1, msg[i]);
		//string temp = msg.substr(i, 1); // 이것을 사용해도 위의 것과 똑같다

        // myMap에서 temp문자열이 있다면, temp 바로 뒤의 문자를 더하여 temp 문자열 길이를 늘린 후 해당 문자가 있는지 계속해서 검사한다.
        // 즉, myMap에 없는 문자가 나올때까지 계속해서 검사한다.
        while(myMap.find(temp) != myMap.end() && i + temp.size() <= msg.size())
        {
            temp += msg[i + temp.size()];
        }

        if (temp.size() > 1) // 만약 찾은 문자열(temp)의 길이가 한 자리보다 크다면(즉 사전에 없는 새로운 조합의 문자열을 찾았다면)                 
        { 
            myMap[temp] = x++; // 그것을 사전(myMap)에 등록한다. 번호는 27부터 차례대로 오름차순으로 등록 
            temp.pop_back();   // 마지막으로 추가한 캐릭터를 제거하여 이전 상태로 되돌린다.
                               //(즉 다음 반복에서 사용할 기존 사전에 이미 등록된 가장 긴 부분문자열을 얻기 위함)
        }
        
         answer.push_back(myMap[temp]); // 현재 단어(temp)의 index 번호를 결과 벡터(answer)에 추가한다.

         i += temp.size();             // 다음 검사 시작 위치(i) 업데이트: 현재 단어(temp)의 길이만큼 건너뛴다.
     }


     return answer;
}

 

 

---