문제
2018 KAKAO BLIND RECRUITMENT - 압축
문제 설명
신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.
어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 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를 출력한다.
현재 입력(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] |
문제 풀이
먼저 Map 객체를 사용해 사전을 만들어준다. 사전을 만들 때는 A
부터 Z
까지의 알파벳을 key로, 1
부터 26
까지의 숫자를 value로 넣어준다.
const map = new Map();for (let i = 0; i < 26; i++) {const char = String.fromCharCode(i + 65);map.set(char, i + 1);}
w
와 c
변수를 초기화한다. w
는 현재 입력된 문자열의 시작 인덱스, c
는 현재 입력된 문자열의 끝 인덱스를 의미한다. w
와 c
를 만들어준 후, msg
의 길이만큼 반복문을 돌려준다.
let w = 0;let c = 0;while (true) {// ...}
반복문의 종료 조건은 c
(마지막 글자의 index)가 msg
의 길이와 같아질 때이다. 이때는 다음 문자를 붙여서 사전에서 찾는 과정이 없으므로, w
부터 c
까지의 문자열을 사전에서 찾아서 answer
에 넣어준다.
c++;if (c === msg.length) {answer.push(map.get(msg.slice(w, c)));break;}
문제에서 설명한 것처럼 w
부터 c
까지의 문자열이 사전에 없다면, w
부터 c - 1
까지의 문자열을 사전에서 찾아서 answer
에 넣어준다. 그리고 c
를 w
로 바꿔주고, c
를 1 증가시켜준다.
slice
메서드는 start 인덱스부터 end 인덱스 전까지의 문자열을 반환한다. 따라서 msg.slice(w, c)
는 w
부터 c - 1
까지의 문자열을 반환한다. 설명이 조금 헷갈릴 수 있으니 주의하자.
const word = msg.slice(w, c + 1);if (!map.has(word)) {map.set(word, map.size + 1);answer.push(map.get(msg.slice(w, c)));w = c;}
코드
function solution(msg) {const answer = [];const map = new Map();for (let i = 0; i < 26; i++) {const char = String.fromCharCode(i + 65);map.set(char, i + 1);}let w = 0;let c = 0;while (true) {c++;if (c === msg.length) {answer.push(map.get(msg.slice(w, c)));break;}const word = msg.slice(w, c + 1);if (!map.has(word)) {map.set(word, map.size + 1);answer.push(map.get(msg.slice(w, c)));w = c;}}return answer;}