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

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

프로그래머스

 

전체 코드

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

vector<int> solution(string msg) {
    vector<int> answer;
    map<string,int> m;
    
    /* A, B, ..., Z 사전 등록 */
    for(int i=1; i<=26; i++)
    {
        string temp;
        temp = 'A'+i-1;
        m.insert({temp, i}); // 문자 A, B, ..., Z와 함께 1, 2, ..., 26 등록
    }
    
    
    int cnt=27; // 사전 추가시 색인 번호는 27부터 시작함.
    while(msg.length()>0){ // 남아 있는 msg가 없을때까지 반복.
        string str; 
        str=msg[0]; // str에 msg의 0번째 인덱스(idx)를 추가함. 이 문자 하나는 사전에 무조건 등록되어있음.
        
        int idx=1; // 인덱스를 늘려가며 사전에 등록된 가장 긴 문자열 w를 찾을 것임. 최종적으로 idx에는 일치하지 않게 되는 첫 문자의 위치를 가질것임.
        for(; idx<msg.length(); idx++) // 1부터 msg의 끝까지 반복함.
        {
            str+=msg[idx]; // 문자 붙여봄
            if(m.find(str)==m.end()) // 붙여봤더니 존재하는 사전에 저장되어 있지 않은걸 발견
            {
                m.insert({str,cnt}); // w+c 등록. 현재 str엔 일치하지 않게되는 문자 하나가 끝에 붙어있음. 결국 그 문자가 다음 글자임.
                cnt++; // 색인 번호 증가
                str.erase(str.begin()+str.length()-1); // 마지막 문자를 제거하여 사전에 존재하는 가장 긴 문자열 w 유지.
                break;
            }
        }
        
        // for문을 나왔을땐 str엔 사전에 존재하는 가장 긴 문자열이 들어 있음. 
        msg.erase(msg.begin(), msg.begin()+str.length()); // str 길이만큼 사전에 등록되어 있으니 msg에서 제거 함.
        answer.push_back(m.find(str)->second); // str의 색인 번호를 찾아 answer에 넣어줌.

    }

    
    return answer;
}

풀이 방법

문제에서 설명한 알고리즘대로 돌아가게끔 코드를 구현하면 된다.

자세한 과정은 주석을 따라 읽으면 된다.

문제가 이해가 안 간다면 LZW 압축에 대해 검색하여 이해하면 그대로 구현하면 된다.