[ 프로그래머스 [ 3차 ] 압축 (Lv2) ] (C++)

프로그래머스의 압축(Lv2) 문제이다.

 

[ 문제풀이 ]

문제에서 제시한 압축과정을 통해서, 압축한 문자열을 사전에 정의하였을 때, 주어진 문자열을 압축한 후의 사전 색인 번호를 출력해야 하는 문제이다.

사전을 정의하는 방법부터, 정답을 도출하는 과정까지 순차적으로 알아보자.

 

#1. 사전에 정의

이 문제에서 가장 핵심적인 부분이다. 주어진 문자열을 사전의 색인 번호로 지정을 해줘야 한다.

즉 ! "문자열"로 이루어진 데이터를 "int형"으로 매핑을 시켜줘야 하는 과정이 필요하다.

본인은 이 과정을 위해서, map이라는 자료구조를 사용했다.

map은 데이터와 이 데이터가 가지는 Key값을 쌍으로 관리해주는 자료구조이다.

본인은 이 맵을 pair<string , int>로 선언을 해서 관리해 주었다. 즉 ! 우리에게 주어진 사전에 정의를 해야 하는 문자열 데이터들을 key값으로, 그리고 해당 key값을 가지는 데이터를 사전의 색인 번호로 관리를 해주었다.

 

map을 선언하고, 가장 초기에는 A ~ Z가 1 ~ 26번으로 매핑이 되어 있으니 이 과정을 코드로 나타내보면 다음과 같다.

int Num = 1;
map<string, int> Dict;

void Make_Default_Dictionary()
{
	for (char C = 'A'; C <= 'Z'; C++)
	{
		string Str = ""; Str += C;
		Dict[Str] = Num++;
	}
}

 

#2. 압축하기

이제 문제의 본론으로 들어가보자. 문제에서 제시한 대로 문자열을 압축을 해야 한다. 이 과정을 다시한번 살펴보자.

1. 사전에서 현재 입력과 일치하는 가장 긴 문자열 W를 찾는다.

2. W에 해당하는 사전의 색인 번호를 출력하고, 입력에서 W를 제거한다.

3. 입력에서 처리되지 않은 단어를 사전에 등록한다.

간단하게 3단계로 나타내보면 위와 같다. 구체적으로 알아보자.

 

주어진 문자열을 토대로, 문자를 하나씩 추가해보면서 우리가 #1의 과정에서 선언해놓은 map에 value를 가지고 있는지를 체크해주면 된다. 만약, value를 가지고 있지 않다면, 해당 문자열은 아직 사전에 등록되지 않았음을 의미한다.

여기서, 우리는 가장 긴 문자열 W를 찾아야 하므로, 문자를 추가할 때 마다 사전에 등록되어 있는 문자열인지 확인을 해보다가, 그렇지 않은 문자열이 등장한다면, 해당 문자열에서 가장 마지막 문자를 하나만 빼주면 된다.

예를 들어보자.

"KAKAO"로 예를 들어보자. 그리고 우리가 탐색할 문자열을 저장할 변수를 'Str' 이라고 가정해보자.

가장 초기의 Str = "" 일 것이다.

가장 처음으로, 'K'를 탐색해보자. 'K'는 이미 사전에 등록되어 있으므로 Str에 추가하자. Str = K

두 번째로, 'A'를 탐색해보자. 'KA'는 사전에 등록되어 있지 않다. 즉 ! 이 경우를 만나게 되면, KA에서 가장 마지막 문자를 하나 뺀 'K'의 색인번호를 출력하면 된다. 그리고 입력에서 'W'를 제거해야한다. 즉 현재 문자열은 "KA"인데, 여기서 사전에 등록되어 있는 가장 긴 문자열인 'K'를 제거하게 되면 결국 Str = A 만 남게 된다.

이렇게 계속해서 반복을 하는 것이다. 이 과정을 코드로 한번 살펴보자.

void Compression(string Str, vector<int> &answer)
{
	string Cur = "";
	for (int i = 0; i < Str.length(); i++)
	{
		Cur += Str[i];
		if (Dict[Cur] == 0)
		{
			Dict[Cur] = Num++;
			Cur = Cur.substr(0, Cur.length() - 1);
			answer.push_back(Dict[Cur]);
			Cur = "";
			i--;
		}
	}
	answer.push_back(Dict[Cur]);
}

간단하게, 위에서 "KA"를 했던 과정만 코드에 빗대어서 이야기해보자.

'Cur' 이라는 변수에 우리가 탐색하고자 하는 문자열을 저장해줄 것이다.

line6)에서, 문자를 하나하나씩 추가해 가는 과정을 볼 수 있다.

line7)에서, 해당 문자열에 사전에 등록되어 있는지 아닌지를 체크해 보는 것이다.

만약, 등록되어 있지 않다면 line7)의 조건문에 들어가게 될 것이다.

아직 등록되어 있지 않다면, 사전에 등록을 해야하므로 line9)에서 사전에 등록을 해주는 것이다.

그리고 ! 우리가 출력해야 하는 색인 번호는, 현재 문자열에서 가장 마지막 문자 하나를 뺀 문자열이라고 했다.

따라서 line10)에서 마지막 문자 하나를 제거해 주는 것이다.

그리고, 문제대로라면, 가장 긴 문자열인 W만 제거를 해야한다. 즉 ! "KA"에서 "K"만 제거하고 "A"를 남겨둬야 하는데,

본인은 간편하게 문자열을 모두 초기화 시켜주었다. 대신 ! 문자열을 탐색하고 있는 변수 i의 값 또한 하나 감소시켜주었다.

이렇게 되면, Str = ""이 될 것이고, 현재 i = 1이라서 'A'까지 탐색을 했지만, i--에 의해서 i가 0이 될 것이다.

이 후, 반복문에 의해 다시 i가 ++가 된다면, 다시 'A'부터 탐색을 시작하게 될 것이다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
int Num = 1;
map<string, int> Dict;
 
void Make_Default_Dictionary()
{
    for (char C = 'A'; C <= 'Z'; C++)
    {
        string Str = ""; Str += C;
        Dict[Str] = Num++;
    }
}
 
void Compression(string Str, vector<int> &answer)
{
    string Cur = "";
    for (int i = 0; i < Str.length(); i++)
    {
        Cur += Str[i];
        if (Dict[Cur] == 0)
        {
            Dict[Cur] = Num++;
            Cur = Cur.substr(0, Cur.length() - 1);
            answer.push_back(Dict[Cur]);
            Cur = "";
            i--;
        }
    }
    answer.push_back(Dict[Cur]);
}
 
vector<int> solution(string msg)
{
    vector<int> answer;
    Make_Default_Dictionary();
    Compression(msg, answer);
    return answer;
}