[프로그래머스] 코딩테스트 연습 - 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;
}

풀고나니 별거 아닌데 시간은 오래 걸렸다
껄껄