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

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

프로그래머스

 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    unordered_map<string, int> um;
    for (int i = 0; i < 26; i++)
        um[string(1, (char)('A' + i))] = i + 1;

    int idP = 0;
    int v = 27;
    while (msg.length() != 0)
    {
        idP = 0;
        string s = "";
        s = msg[idP];
        while (um.find(s) != um.end())
        {
            s += msg[++idP];
        }
        um.insert({ s,v++ });
        msg = msg.substr(s.length() - 1);
        answer.push_back(um[s.substr(0,s.length()-1)]);
    }

    return answer;
}

처음 이코드로 문제를 풀었다. 

unordered_map 을 통해서 사전을 만들고 

while문을 통해서 사용한 입력은 msg에서 지우는 방식이다. 

두번째 while문은 s가 사전에 없을 때까지 s를 늘린다. 

그리고 substr을 통해서 s를 사전에 넣고 출력한다. 

이 때, substr은 o(n)의 시간복잡도를 가진다. 또 msg를 대부분 잘라내는 입력일 경우 즉, 최악의 경우 시간복잡도가 O(n^2)이다. 

 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    unordered_map<string, int> um;
    for (int i = 0; i < 26; i++)
        um[string(1, (char)('A' + i))] = i + 1;

    int v = 27;
    string w="";
    for(int i=0;i<msg.length();i++)
    {
        w+=msg[i];
        if(um.find(w)==um.end())
        {
            um[w]=v++;
            w.pop_back();
            answer.push_back(um[w]);
            w=msg[i];
        }
    }
    answer.push_back(um[w]);
    return answer;
}

chat gpt 는 이렇게 O(n)의 방식으로 문제를 해결했다. 

굳이 while문으로 없는것을 찾아서 인덱스를 늘리고 substr로 msg를 변경할 필요없이 이 모든것을 for문 하나로 처리했다. 

w에 msg[i]를 추가해가면서 만약 사전에 없으면 사전에 추가하고 출력한다. 

w.pop_back 이란 함수가 있는줄 알았으면 좀 더 쉽게 접근했을 것 같다. 

너무 복잡하게 생각한게 독이 된것같다.