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

문제

---

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

풀이

---

LZW 압축 과정을 그대로 구현하는 문제로,

1. 길이가 1인 모든 단어를 포함하도록 사전 초기화.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 대한 색인 번호를 answer에 담는다.
4. w + 처리되지 않은 다음 글자에 해당하는 단어를 사전에 등록한다.
5. 2번부터 다시 반복한다.

이를 그대로 구현한다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<string>alphabet;
    string s_alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    for (int i = 0; i < 26; ++i)
    {
        string s;
        s = s_alphabet[i];
        alphabet.push_back(s);
    }

    string origin = msg;
    int max_idx = 0;

    while (origin.size() != 0)
    {
 
        for (int i = 0; i < origin.size();++i)
        {
            string s = origin.substr(0, origin.size() - i);

            auto it = find(alphabet.begin(), alphabet.end(), s);

            if (it != alphabet.end())
            {
                answer.push_back(it - alphabet.begin() + 1);
                s += origin[alphabet[it - alphabet.begin()].size()];
                alphabet.push_back(s);

                origin = origin.substr(s.size() - 1, origin.size());
                break;
            }

            else
            {
                s.pop_back();
            }

        }
    }

    return answer;
}