[프로그래머스] 코딩테스트 연습 - 63
level 2 - 압축
어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.
LZW 압축은 다음 과정을 거친다.
1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.
주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.
입출력 예시
m : TOBEORNOTTOBEORTOBEORNOT
-> [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]
function solution(msg) {
var answer = [];
var dict = [];
for(var i=0; i<msg.length; i++) {
var start = i;
var size = 1;
var idx = msg[i].charCodeAt() - 64;
var pre = msg[i];
while(dict.includes(msg.slice(start, start+size+1)) && i < msg.length) {
pre = msg.slice(start, start+size+1);
size++;
i++;
}
if (size > 1) idx = 27 + dict.indexOf(pre);
dict.push(msg.slice(start, start+size+1));
answer.push(idx);
}
return answer;
}
풀고나니 별거 아닌데 시간은 오래 걸렸다
껄껄
Author And Source
이 문제에 관하여([프로그래머스] 코딩테스트 연습 - 63), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@krkorklo58/프로그래머스-코딩테스트-연습-63저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)