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

문제 바로가기

접근 방식

문제가 길다... but 간단한 문제다. 원래 있는 단어면 그 단어에 해당하는 index출력이고 없는 단어면 새로 등록해주면 된다.
우선 어떻게 문제를 해결할지 단계를 짜봤다.

1. A - Z 인덱스로 짝 지어진 map 구현
2. 새로운 단어 찾으면 맵에서 검색후 없으면 인덱스와 함께 map에 추가
3. 나온 숫자 answer에 추가

기본적으로 A - Z 는 1 ~ 26 index와 짝지어져 있다. 이렇게 단어와 숫자가 쌍으로 되어있으면서 검색이 유용하고 추가가 편리한 자료구조가 뭐가 있을지 생각해보다가 map을 떠올렸다.

1번 initializer함수에서 실행이된다. map에 [알파벳, index] 쌍이 들어간다.
2번 과정은 i번째 index에서 j개의 개수씩 substr을 통해 단어를 구하고, 이 단어가 map안에 없다고 나올 때 까지 반복을 해준다.
여기서 map의 find를 써서 있는지 없는지 확인하는것 말고 [ ]연산자를 활용하였다.
예를들어 "pinako"가 map안에 없을 때
map["pinako"]를 해주면 해당 단어가 없으니까 새로 "pinako"를 넣어주는데, index가 정해지지 않았으므로 0으로 초기 세팅하게 되는것이다.(즉 map안에 ["pinako",0] 쌍이 들어갔다는 뜻이다.)

그리하여 0이 나온 번째까지의 단어는 map에 새로이 추가
그리고 0이 나오기 바로 직전 단계의 단어는 원래 map에 있었다는 뜻이므로 answer에 추가해주었다.

3번과정에선 하나 예외상황이 있었다.
msg의 마지막index까지 map에 있는 단어라면 answer에 추가를 못하는 경우가 발생하기에
i + j가 msg의 길이와 같아질때까지 갔다면 해당단어의 index를 answer에 추가하도록 예외처리를 해주었다.

코드

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

using namespace std;
map <string, int> wordList;
void initializer(){ //A - Z // 1 - 26 쌍으로 넣어줌
    char ss;
    string str;
    for(int i = 0 ; i < 26; i++){
        ss = 'A';
        str = "";
        str += (ss + i);
        wordList[str] = i + 1;
    }
}
vector<int> solution(string msg) {
    vector<int> answer;
    initializer(); //1번과정
    int index = 26, leng = msg.length();
    for(int i = 0; i < leng; i++){//i는 msg에서의 index
        for(int j = 1; j <= leng - i ; j++){ //j는 i번째 부터 확인할 단어의 길이
       		string check = msg.substr(i,j);
            if(wordList[check] == 0){
                answer.push_back(wordList[msg.substr(i,j-1)]);
                wordList[check] = ++index;
                i += (j-2);
                break;
            }
            if((i + j) == leng) {
                answer.push_back(wordList[check]);
                i += j;
                break;
            }
        }
    }
    return answer;
}
``