[프로그래머스][Level2] 압축

문제

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

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

현재 입력(w)   다음 글자(c)   출력	사전 추가(w+c)
   K            A         11	  27: KA
   A		K	   1	  28: AK
   KA		O	  27	  29: KAO
   O			  15	

코드

function solution(msg) {
    var answer = [];
   let dic = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split('');
   let l = msg.length;
   
   while(msg.length>0){
        for(let i=l; i>0; i--){
             let word_index = dic.findIndex(d => {return d === msg.substr(0, i)});
             if(word_index >= 0){
                 let w = msg.substr(0, i);
                 let c = msg.substr(i, 1);
                 if(c.length > 0) {   
                    dic.push(w+c);
                 } 
                 answer.push(word_index+1);
                 msg = msg.substr(i, msg.length);
                 break;
            }
        } 
   }


    return answer;
}

방법

1. KAKAO -> KAKA -> KAK -> KA -> K 순서로 사전을 찾음
2. w = 사전에서 검색되는 단어(K)
   c = w+1 (A)
3. w+c를 사전에 넣고, w의 index를 answer에 push
4. k가 제거된 문자열 msg 재설정함

후기

체감난이도 ; ⭐️⭐️