[3차] 압축(2018 카카오 블라인드 채용)

문제 링크

코딩테스트 연습 - [3차] 압축

 

 

풀이

첫 번째로 사전 초기화를 하였고, 이는 map으로 하였다. 중복이 없어야된다고 생각했다?

그리고 // TODO 부분에서부터는

map.find() 함수를 이용하여 못찾았을 때는 map.end()와 같을 점을 이용했다.

그리고, 찾았던 곳까지 index를 출력하고 못찾은 것은 사전에 등록하였다.

 

[요약]

사전 초기화;

반복문(){

    반복문(){

        출력용 변수 대입;

        다음 문자랑 합침

        비교; --- 못찾으면 탈출

    }

    출력용

    사전 등록

}

 

 

 

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

using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    map<string, int> dic;   // dictionary
    
    // 사전 초기화
    for(int i=0; i<26; i++){
        string s;
        s.push_back('A'+i);
        dic[s] = i+1;
    }
    
    // TODO
    map<string, int>::iterator iter;
    for(int i=0; i<msg.length(); i++){
        int index;
        string w = "";
        for(int j=i; j<msg.length(); j++){
            w += msg[j];
            iter = dic.find(w);
            if(iter == dic.end()) break;      // 못찾았다.
            i=j;
            index = iter->second;
        }
        answer.push_back(index);        // 출력 추가
        dic.insert(make_pair(w, dic.size()+1));     // 사전 추가
    }
    
    return answer;
}