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

해설

문제의 의미를 파악하는데 꽤 시간이 걸리는 문제이다.

현재 입력과 일치하는 가장 긴 문자열을 찾으라는 것은, 현재 문자열의 0번째 인덱스부터 특정 인덱스까지가 사전에 있는지 확인하고, 사전에 있는 문자열 중 가장 긴 것을 택하라는 의미이다.

예를 들어 HELLOWORLD라는 문자열이 주어진다면, HELLOWORLD, HELLOWORL, HELLOWOR, HELLOWO, ... , H까지의 문자열 중 사전에 있는 가장 긴 문자열을 찾으라는 것이다.

 

문자열을 찾은 뒤에는 문제에서 주어진 대로 사전의 색인번호를 결과 벡터에 추가한다.

이후 w+c 단어를 사전에 등록한 뒤, 현재의 문자열에서 사전에 있는 단어를 제거하면 된다.

 

 

전체 코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <climits>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second


vector<int> solution(string msg) {
    
    //길이가 1인 모든 단어를 포함하도록 사전 초기화
    vector<string> w(27);
    w[0] = "";
    for (int i=1; i<=26; i++) w[i] = string(1, 'A'+(i-1));

    vector<int> ret;
    while (msg.size()) {
        
        int idx = 0;
        int sz = msg.size(), wsz = w.size();

        //현재 입력과 일치하는 가장 긴 문자열을 찾아 사전의 색인번호를 idx에 저장
        for (int i=sz; i>=1; i--) {
            string s = msg.substr(0, i);
            for (int j=1; j<wsz; j++) {
                if (w[j] != s) continue;
                idx = j;
                break;
            }
            if (idx != 0) break;
        }
        
        ret.push_back(idx);

        //w+c 단어를 사전에 등록
        if (w[idx].size() < msg.size()) w.push_back(w[idx]+msg[w[idx].size()]);

        //입력에서 w 제거
        msg.erase(msg.begin(), msg.begin()+w[idx++].size());
    }
    
    return ret;
}