[카카오 공채] 압축

[문제] 신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

LZW 압축은 다음 과정을 거친다.

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.

색인 번호	1	2	3	…	24	25	26
단어	A	B	C	…	X	Y	Z

예를 들어 입력으로 KAKAO가 들어온다고 하자.

1. 현재 사전에는 KAKAO의 첫 글자 K는 등록되어 있으나, 두 번째 글자까지인 KA는 없으므로, 첫 글자 K에 해당하는 색인 번호 11을 출력하고, 다음 글자인 A를 포함한 KA를 사전에 27 번째로 등록한다.
2. 두 번째 글자 A는 사전에 있으나, 세 번째 글자까지인 AK는 사전에 없으므로, A의 색인 번호 1을 출력하고, AK를 사전에 28 번째로 등록한다.
3. 세 번째 글자에서 시작하는 KA가 사전에 있으므로, KA에 해당하는 색인 번호 27을 출력하고, 다음 글자 O를 포함한 KAO를 29 번째로 등록한다.
4. 마지막으로 처리되지 않은 글자 O에 해당하는 색인 번호 15를 출력한다.

현재 입력(w)	다음 글자(c)	출력	사전 추가(w+c)
K	A	11	27: KA
A	K	1	28: AK
KA	O	27	29: KAO
O		15

이 과정을 거쳐 다섯 글자의 문장 KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축된다.

입력으로 TOBEORNOTTOBEORTOBEORNOT가 들어오면 다음과 같이 압축이 진행된다.

현재 입력(w)	다음 글자(c)	출력	사전 추가(w+c)
T	O	20	27: TO
O	B	15	28: OB
B	E	2	29: BE
E	O	5	30: EO
O	R	15	31: OR
R	N	18	32: RN
N	O	14	33: NO
O	T	15	34: OT
T	T	20	35: TT
TO	B	27	36: TOB
BE	O	29	37: BEO
OR	T	31	38: ORT
TOB	E	36	39: TOBE
EO	R	30	40: EOR
RN	O	32	41: RNO
OT		34

[입출력 예제]

입력으로 영문 대문자로만 이뤄진 문자열 msg가 주어진다. msg의 길이는 1 글자 이상, 1000 글자 이하이다.

주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.

msg	answer
KAKAO	[11, 1, 27, 15]
TOBEORNOTTOBEORTOBEORNOT	[20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]
ABABABABABABABAB	[1, 2, 27, 29, 28, 31, 30]

[풀이를 위한 개념]

LZW라는 압축방식을 이용한 문제풀이입니다. 하지만 LZW가 뭔지 몰라도 어떤방식으로 출력이 이뤄지는지 알면 그 용어는 알지 못해도 상관 없습니다.

문제를 요약하자면 A~Z가 초기 저장된 사전에 저장되어 있는 알파벳 혹은 알파벳 조합이 있으면 그에 해당하는 숫자를 출력하고 없으면 사전에 추가합니다.

즉, 사전에서 단어를 검색하고 없으면 추가하는 간단한 방식입니다.

알파벳이 될 수도 있고 알파벳의 조합이 될 수도 있으므로 string 자료구조를 사용하겠습니다.

string 구조는 char + char 형태의 연산도 가능합니다.

사전검색과 사전추가는 단순히 반복문을 사용하면 됩니다.

입력 단어는 1000자 이하로 주어지고 단어 하나에 사전을 검색하는 구조로 나타낼 수 있으므로  최대 1000x1000의 경우의 수가 나옵니다. 충분히 작은 데이터이므로 단순 반복문을 사용하겠습니다.

[풀이과정] 

의사코드로 작성하면 조금더 쉽게 풀과정을 생각할 수 있습니다.

1. 첫번째 단어를 꺼내온다. ('KAKAO'일 경우 'K'를 꺼내온다.)

2. 첫번째 단어가 사전에 있을 경우, 두번째 단어와 합친 단어가 있는지 다시 검색한다. ('KAKO'일 경우 'KA'가 있는지 검색한다)

3. 없을 경우 단어를 추가하고 두번째 단어부터 1번 순서로 진행한다.

이번에는 'KAKAO'가 예제입력으로 주어질 때, 문제풀이 과정을 그려보겠습니다.

[그림1] 단어를 검사하고 추가하고 검사하고 추가하고 검사하는 과정이다. 사전에 없을 경우에는 추가한 단어를 모두 없애고 다시 초기화 한다.

[그림1]에서 포인트는 빨간색 상자들(사전에서 찾지 못한 경우, false)일 경우 이어서 검사할 알파벳은 단어의 맨 끝 알파벳이라는 점입니다.. 단어의 자리를 표시해주는 index를 i라고 할 때, 사전검색이 true일 경우에만 i++를 취해주면 해당 자리의 단어로 초기화 할 수 있습니다..

(i = 0 이고 string s = 'KAKAO' 일 때, 

1. 'K'는 s[0], true이므로 i++

2. 'KA'는 s[0] + s[1], false 이므로 i는 그대로 1

3. 'A'는 s[1], true이므로 i++

4. 'AK'는 s[1] + s[2], false 이므로 i는 그대로 2

5. 'K'는 s[2], true이므로 i++

6. 'KA'는 s[2] + s[3], true이므로 i++

7. 'KAO'는 s[2] + s[3] + s[4], false이므로 i는 그대로 4

8. 'O'는 s[4], false이므로 i는 그대로 4

)

두번째 포인트는 사전자리 출력을 false일 때만 해주는 것입니다. [그림 1]을 보면 빨간색 상자 앞에 있는 파란색 상자의 출력값만 나열해야 정답과 같아집니다. 즉 true일 때마다 출력하면 'K'일 때와 'KA'의 사전값을 모두 출력하므로 정답이 나오지 않습니다. 이렇게 되면 문제가 마지막 'O'일 때는 뒤에 빨간색 박스가 없으므로 출력을 하지 못하게 되는데, 이 부분만 true일 때 조건문으로 추가할 수 있도록 장치를 마련해주면 됩니다. 코드를 보면 쉽게 이해될 것입니다.

[정답] 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
 
using namespace std;
 
string a[] = {"","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"};
 
vector<string> v(&a[0], &a[27]);    //배열을 사전 벡터에 통채로 넣기
 
string temp = "";                    //검색단어를 넣을 string
 
 
 
int dict(string s)                    //검색과정
{
    for(int i = 0; i < v.size(); i++)
    {
        if(s == v[i])
        {
            return i;                //찾으면 사전값을 출력
        }
 
    }
    return -1;                        //못찾으면 -1 출력
}
 
int main()
{
 
    string msg = "";                //입력받을 단어
    cin >> msg;
 
    vector<int> answer;                //사전값을 나열한 최종정답(벡터형)
    int i=0;                        //단어위치를 보여주는 i값
    int result;                        //answer 벡터에 넣을 때 필요한 순간 사전값
    int index;                        //dict() 함수에서 나온 index값
    int ans;
 
    temp = msg[i];                    //입력받은 msg의 첫번째, msg[0]부터 출발
    while(i < msg.size())
    {
        index = dict(temp);
        if(dict(temp) > -1)                //사전에서 찾은 경우
        {
            ans = index;                //사전에서 찾은 경우, 사전값을 미리 저장해놓는다. (나중에 false일 때 추가하기 위해서)
 
            if(i == msg.size() -1)        //맨 마지막 단어를 위한 장치
            {
                answer.push_back(ans);
            }
            i++;
            temp += msg[i];                //다음 단어추가
        }
        else                            //사전에서 못찾은 경우
        {
            answer.push_back(ans);    //[그림 1]에서 빨간박스 앞에 있는 파란박스의 사전값만 추가하기 위함.
            v.push_back(temp);        //없는 단어 추가한뒤
            temp = msg[i];            //이어지는 단어로 초기화
        }
 
    }
 
    for(int k = 0; k < answer.size(); k++)
    {
        cout << "answer"<<endl;
        cout << answer[k] << endl;
    }
 
 
}