[프로그래머스] 압축 - 자바스크립트

문제

코딩테스트 연습 - [3차] 압축

 

코드

function solution(msg) {
  const answer = [];
  const dict = [0];
  for (let i = 0; i < 26; i++) {
    dict.push(String.fromCharCode(i + 65));
  }

  let idx = 0;
  let w = msg[idx];
  while (true) {
    let c = msg[++idx];
    if (c === undefined) {
      answer.push(dict.indexOf(w));
      return answer;
    }
    if (dict.includes(w) && !dict.includes(w + c)) {
      answer.push(dict.indexOf(w));
      dict.push(w + c);
      w = c;
    } else {
      w += c;
    }
  }
}

 

풀이

 

LZW 압축 과정

 

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

 

변수 w,c는 각각 문제에 주어진 검증 문자열 w, 다음 문자 c를 의미한다.

     

사전에 w가 존재하고 w+c가 존재하지 않을 때

      사전에서 w의 인덱스를 정답 배열에 기록하고, 사전에 w+c를 추가하고, w를 c로 변경한다.

사전에 w가 존재하고 w+c도 존재한다면 w를 w+c로 변경한다.

 

두 절차 모두 다음 문자열 c를 요구하므로, while문의 첫 라인에서 변수 c를 받는다.

 

c가 존재하지 않는다면 더이상 진행할 수 없으므로 현재 w를 출력하고 무한루프를 종료한다.

무한루프를 종료하면서 w의 사전 인덱스를 담은 배열을 출력한다.