[Programmers] 압축

새로운 문자열을 배열에 추가하며 찾는 문제이다.

문제 해결 전략
문자열을 저장한 배열에 새로운 문자열이 있는지 확인 후 없으면 배열에 추가해야 한다.

즉, 매번 배열을 탐색하며 문자열의 존재 유무를 확인해야 한다는 것이다.

이 과정을 쉽게하기 위해 map 자료구조를 이용하였다.

map은 find 함수를 제공하기 때문에 배열을 순차적으로 탐색하는 것보다 시간복잡도도 낮고 사용하기도 쉽다.

문자열이 map에 존재하는지 확인 후 존재한다면 문자열 늘린다.

만약 존재하지 않는다면 늘리기 전 문자열을 map에 추가 하는 것이다.

코드

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

using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    map<string, int> m;
    for(int i=1;i<27;i++){
        string alpha = "";
        char tmp = 'A' + i - 1;
        alpha += tmp;
        m.insert(make_pair(alpha, i));
    }
    
    for(int i=0;i<msg.size();i++){
        string str = "";
        str += msg[i];
        int tmp = 0;
        while(1){
            if(m.find(str) != m.end()){
                tmp = m[str];
                i++;
                str += msg[i];
            }else{
                answer.push_back(tmp);
                m.insert(make_pair(str,m.size()+1));
                i--;
                break;
            }
        }
    }
    
    return answer;
}

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