(C++) - 프로그래머스(2018 KAKAO BLIND RECRUITMENT[3차]) : 압축

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

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

구현 문제였습니다.

 

풀이방법

 1. 사전에 등록되어있다면 현재 문자열을 string 변수 w 계속 붙여줍니다. 사전에 등록되어 있지 않다면 등록이 되었었던 가장 긴 문자열을 answer에 push해주고 piv를 현재 index로 갱신해줍니다. 그 후 w+msg[j]문자열은 등록이 안되어있으므로 map에 등록해줍니다. 그리고 break합니다.

 

 2. piv부터 msg의 끝까지 잉여 문자열을 substr해 surplus 변수에 저장합니다. 만약 잉여 문자열이 등록되어있던 문자열이라면 answer에 해당 값을 push해줍니다. 아닌경우에는 ++cnt를 push해줍니다. cnt는 등록번호 변수입니다.

 

 

Code

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    map <string,int> m;
    int cnt = 0, piv = 0;
    string w ="";
    for(int i = 0; i < 26; i++){
        string s(1,'A' + i);
        m[s] = ++cnt;
    }
    for(int i = 0; i < msg.size(); i++){
        string w(1,msg[piv]);
        for(int j = piv + 1; j < msg.size(); j++){
            if(m[w + msg[j]]) w += msg[j];
            else{
                answer.push_back(m[w]);
                piv = j;
                m[w+msg[j]] = ++cnt;
                break;
            }
        }
    }
    string surplus = msg.substr(piv);
    if(m[surplus]) answer.push_back(m[surplus]);
    else answer.push_back(++cnt);
    return answer;
}

 

Test Case

반례입니다.

input : "A"

답 : [1]