문제 설명
신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다.
메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.
어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel-Ziv-Welch)
압축을 구현하기로 했다.
LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.
LZW 압축은 다음 과정을 거친다.
- 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
- 사전에서 현재 입력과 일치하는 가장 긴 문자열
w
를 찾는다. w
에 해당하는 사전의 색인 번호를 출력하고, 입력에서w
를 제거한다.- 입력에서 처리되지 않은 다음 글자가 남아있다면(
c
),w+c
에 해당하는 단어를 사전에 등록한다. - 단계 2로 돌아간다.
압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수 값으로 주어지며, 1부터 시작한다고 하자.
색인 번호 | 1 | 2 | 3 | … | 24 | 25 | 26 |
---|---|---|---|---|---|---|---|
단어 | A | B | C | … | X | Y | Z |
예를 들어 KAKAO
가 들어온다고 하자.
-
현재 사전에는
KAKAO
의 첫 글자K
는 등록되어 있으나, 두 번째 글자까지인KA
는 없으므로, 첫 글자K
에 해당하는 색인 번호 11을 출력하고, 다음 글자인A
를 포함한KA
를 사전에 27 번째로 등록한다. -
두 번째 글자
A
는 사전에 있으나, 세 번째 글자까지인AK
는 사전에 없으므로,A
의 색인번호 1을 출력하고,AK
를 사전에 28번쨰로 등록한다. -
세 번째 글자에서 시작하는
KA
가 사전에 있으므로,KA
에 해당하는 색인 번호 27을 출력하고 다음 글자O
를 포함한KAO
를 29번째로 등록한다. -
마지막으로 처리되지 않은 글자
O
에 해당하는 색인 번호 15를 출력한다.
입출력 예제
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] |
Solution
문제 풀이를 위해 필요한 자료구조는 Stack
과 Map
이다.
Stack
의 경우 문자를 하나씩 추출하며, 이어진 문자열이 사전에 존재하는지 확인 후 존재하지 않는 문자열이 될 때 까지 계속해서 추출한다.
Map
의 경우 사전을 구현하기 위한 자료구조로써, Stack
으로 부터 뽑아 이어진 문자열들의 색인 번호를 저장한다.
문제를 잘 읽고 그대로 구현만 한다면 쉽게 풀리는 문제이다.
Code
몇줄 평
필요한 자료구조를 판단하고 기본적인 구현력이 필요한 문제였다.