[알고리즘] 프로그래머스_압축

본 블로그는 비상업적, 비영리적 용도의 학업만을 위해 글을 게시합니다.

1. 문제 분석

• 문자열을 순차적으로 읽으면서, map에 등록안된 key가 될 때까지 현재 입력(w)를 구하고, map에 등록하면 될 것 같다.
• 문자열의 범위를 넘어가지 않게 조절만 하면 될 것 같다.

2. 문제 풀이 과정(삽질)

• X

3. 문제 해결

• 기본 알파벳으로 map을 초기화 한다.
• 이후 주어진 조건대로 한다.
• 문제에 주어진 대로 현재 입력과 다음 글자로 나누어서 하면 더 괜찮을거 같은데, 일단 하나의 key 변수로 처리해봤다.

4. 코드

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;
bool isRegistered(map<string, int> LZW, string key)
{
    if(LZW.count(key))
        return true;
    
    return false;
}
    
vector<int> solution(string msg) {
    int value = 27, length = 1;;
    vector<int> answer;
    map<string, int> LZW;
    for(int i = 0; i < 26;)
    {
        string s(1, 'A' + i);
        LZW[s] = ++i;
    }
    
    for(int i = 0; i < msg.length();)
    {
        string key(1, msg[i]);
        while(isRegistered(LZW, key))
        {
            key += msg[++i];
            if(i == msg.length())
                break;
        }
        if(isRegistered(LZW, key))
        {
            answer.push_back(LZW[key]);
        }
        else
        {
            LZW[key] = value++;
            answer.push_back(LZW[key.substr(0, key.length() - 1)]);
        }
    }
    // for(auto i : LZW)
    //     cout << '{' << i.first << ':' << i.second << "} ";
    // cout << '\n';
    // for(auto i : answer)
    //     cout << i << ' ';
    // cout << '\n';
    return answer;
}