[프로그래머스] 압축 c++

압축 문제 링크 

 

리뷰 

사전에는 A부터 Z까지 들어있는데, 없는 문자열을 만나면 사전에 추가해야 한다. 

사전에 문자열이 있나 없나 확인할 연산이 많으니까 사전 자료구조는 map을 썼다. 

map < 문자열 string , 색인번호 int >  dic ;

 

사전에서 탐색할 문자열은 target 스트링에 한 글자씩 이어붙여서 만든다. 

 

예제의 입력 "KAKAO" 가 있다. 

K는 사전에 존재하지만, KA는 사전에 없다. 

if(dic.find(target) == dic.end())  조건문 에 만족하게 된다. 

사전에 없는 KA를 넣는다.  dic[target] = num++;

 

KA 말고, 그 직전 문자 K는 사전에 존재한다는 거니까. target 문자열에서 길이 1개가 짧은 문자열 K을 answer에 추가한다.

 

여기서 중요한건 target이라는 탐색 문자열을  ""로 초기화 해야된다는 것이다. 

target 문자열 "KA"는 입력문자열 "KAKAO"의 0번째와 1번째 문자를 이어붙인 것이다. 

 

K, KA를 확인했으니 이제 A를 확인할 차례다. 

따라서 KA라는 없던 문자열을 사전에 추가했으니, 이어붙일 단어의 인덱스는 A의 인덱스 1이 되어야 한다. 

i--  로 target 문자열에 이어붙일 인덱스를 감소시켜줘야 한다. 

 

 

"맞았습니다" 코드 

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

map<string,int> dic; // {단어, 색인 번호}
int num = 1; // 색인 번호 

void init_dictionary(){
  char ch = 'A';
  for(; ch <= 'Z'; ch++, num++){
    string st = ""; st += ch;
    dic[st] = num;
  }
}

vector<int> solution(string msg) {
  vector<int> answer;

  init_dictionary();
  int len = msg.length();
  int start_idx = 0;

  string target = "";
  for(int i = 0; i < len; i++){ // 탐색 시작할 인덱스 i
    target += msg[i]; // 탐색할 문자

    if(dic.find(target) == dic.end()){
      dic[target] = num++; // 사전에 등록

      target = target.substr(0, target.size()-1);
      answer.push_back(dic[target]);
      target = "";
      i--;
    }
  }
  answer.push_back(dic[target]); // 마지막 글자 
  return answer;
}