[알고리즘 C++][3차] 압축

오늘의 문제

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

압축

나의 풀이

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

using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    map<string, int> dic;
    int num = 1;
    for(;num<27;num++){
        char put = 'A' + (num-1);
        string s;
        s.push_back(put);
        dic[s] = num;
    }
    while(msg.size()!= 0){
        for(int i=1;i<=msg.size();i++){
            string sub = msg.substr(0, i);
            if(dic[sub] == 0){ // 없으면
                dic[sub] = num++;
                string pre = msg.substr(0, i-1);
                answer.push_back(dic[pre]);
                msg = msg.substr(i-1, msg.size()-pre.size());
                break;
            }else{
                if(msg.size() == i){
                    answer.push_back(dic[msg]);
                    msg = "";
                }
            }
        }
    }  
    return answer;
}

모범 답안

#include <string>
#include <vector>

using namespace std;

int search(vector<string> &dictionary, string msg)
{
    int len = dictionary.size();
    for (int i = 1; i < len; i++)
    {
        if (msg == dictionary[i])
            return i;
    }
    return -1;
}

vector<int> solution(string msg) 
{
    vector<int> answer;
    int len = msg.length();
    vector<string> dictionary = { "-1" };

    for (int i = 0; i < 26; i++)
    {
        dictionary.push_back(string(1, 'A' + i));
    }

    int cur = 0;
    int checkLen = 1;
    int idx = -1;

    while (true) 
    {
        string str = msg.substr(cur, checkLen);     
        int tmp = search(dictionary, str);

        if (tmp > 0)//hit
        {
            idx = tmp;
            checkLen++;
            if (cur + checkLen - 1 == len)
            {
                answer.push_back(idx);
                break;
            }
        }
        else//miss
        {
            answer.push_back(idx);
            dictionary.emplace_back(str);
            cur += checkLen-1;
            checkLen = 1;
            idx = -1;
        }
    }
    return answer;
}

배울 점

• 굳이 map을 안쓰고 dictionary를 만들었는지 모르겠다
• string(1, 'A' + i); // char를 string으로 받는 법