프로그래머스 JS [압축] 재귀

[3차] 압축 문제 보기

압축

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

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

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

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

색인 번호123...242526

단어

A

B

C

...

X

Y

Z

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

K	A	11	27: KA
A	K	1	28: AK
KA	O	27	29: KAO
O		15

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

---

문제 풀이 어제 문제를 풀며 배운 재귀로 종료조건과 할 일을 선언하여 풀어보았습니다.         종료조건: 다음글자가 없을 때, 현재입력의 인덱스를 결과에 추가하고 종료해         if (다음글자 === undefined) {             indexArray.push(indexObject[현재입력]);             return;         }        일 한 번에 진행도를 1씩 올릴거야        progress++;         할일: 현재입력과 다음글자를 합친글자가 indexObject에 있는지 확인해.         const 합친글자 = 현재입력 + 다음글자;         const 합친글자있냐 = indexObject[합친글자] !== undefined;           => 있으면: 합친글자랑 다음 글자를 합친 글자가 indexObject에 있는지 확인하는걸 계속해.         if (합친글자있냐) {             zip(합친글자, msg[progress + 1]);         => 없으면: indexObject의 마지막에 합친글자를 추가하고         indexArray에 현재입력의 index를 추가하고, 다음 글자에 같은 작업을 수행해         } else {             indexObject[합친글자] = Object.keys(indexObject).length + 1;             indexArray.push(indexObject[합친글자.slice(0, -1)]);             zip(msg[progress], msg[progress + 1]);         }

function solution(msg) {     const alphabetArray = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");     const indexObject = new Object();     alphabetArray.forEach((alphabet, forIndex) => {         indexObject[alphabet] = forIndex + 1;     });     const indexArray = [];     let progress = 0;     const zip = (현재입력, 다음글자) => {         if (다음글자 === undefined) {             indexArray.push(indexObject[현재입력]);             return;         }         progress++;         const 합친글자 = 현재입력 + 다음글자;         const 합친글자있냐 = indexObject[합친글자] !== undefined;         if (합친글자있냐) {             zip(합친글자, msg[progress + 1]);         } else {             indexObject[합친글자] = Object.keys(indexObject).length + 1;             indexArray.push(indexObject[합친글자.slice(0, -1)]);             zip(msg[progress], msg[progress + 1]);         }     };     zip(msg[progress], msg[progress + 1]);     return indexArray; } solution("KAKAO");