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

programmers.co.kr/learn/courses/30/lessons/17684

코딩테스트 연습 - [3차] 압축

<풀이>

1. 문자열을 주어진 LZW 압축 과정에 따라 압축한다.

2. 압축이 모두 완료된 후, 색인 번호들을 반환한다.

 

<해법>

문제를 푸는데 특별한 아이디어가 필요하지 않습니다. 주어진 LZW 압축 과정을 정확하게 구현하는 것이 문제의 핵심이라고 생각합니다. 저는 주어진 압축 과정을 최대한 똑같이 구현하는데 초점을 두어서 구현하였습니다.

 

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
//사전
vector<string> dict;
 
//메시지 안에 같은 단어가 있는지 확인
bool hasSameVocab(string msg, string vocab) {
 
    for (int i = 0; i < vocab.length(); i++) {
        if (vocab[i] != msg[i]) {
            return false;
        }
    }
 
    return true;
}
 
vector<int> solution(string msg) {
    vector<int> answer;
 
    /*
    1. 사전 만들기
    */
    dict.push_back("#");
    for (int i = 0; i < 26; i++) {
        char alpha = 'A' + i;
        dict.push_back(string(1, alpha));
    }
 
    /*
    2번 ~ 5번 반복
    */
    while (true) {
 
        /*
        2. 사전에서 입력과 일치하는 가장 긴 문자열 찾기
        */
        string removeVocab = ""; //지워지는 단어
        int index; //사전 색인
 
        //사전을 모두 탐색
        for (int i = 1; i < dict.size(); i++) {
 
            string vocab = dict[i];
 
            //메시지안에 같은 단어가 있고, 길이가 더 긴 단어 지우기
            if (hasSameVocab(msg, vocab) && vocab.length() > removeVocab.length()) {
                removeVocab = vocab;
                index = i;
            }
        }
 
        /*
        3. 색인 번호 담고, 메시지에서 해당 단어 지우기
        */
        answer.push_back(index);
        msg = msg.substr(removeVocab.length());
 
        /*
        4. 다음 글자가 남아 있을 경우, 다음 글자 포함해서 사전 등록
        */
        if (msg.empty()) {
            break;
        }
        else {
            dict.push_back(removeVocab + msg[0]);
        }
    }
 
    //결과 반환
    return answer;
}

 

구현에 대해서 알아볼 수 있는 문제였습니다.