[프로그래머스] 카카오 - 압축

문제

2018 카카오 블라인드 채용 - [3차] 압축

https://school.programmers.co.kr/learn/courses/30/lessons/17684

 

 

풀이

설명

주어진 문자열을 압축한 후의 사전 색인 번호를 구하는 문제입니다.

 

압축 알고리즘은 LZW를 사용합니다.

 

압축 방법은 다음과 같습니다.

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

 

투 포인터를 사용해 가장 긴 문자열을 관리합니다.

 

예시 코드

function solution(msg) {
  const ALPHABET_COUNT = 26;
  const ASCII_A = 65;

  const dict = new Map();
  const answer = [];

  for (let i = 0; i < ALPHABET_COUNT; i++) {
    const ch = String.fromCharCode(i + ASCII_A);
    dict.set(ch, i + 1);
  }

  let [start, end] = [0, 1];
  let str = "";

  while (end <= msg.length) {
    str = msg.slice(start, end);
    if (dict.has(str)) end++;
    else {
      dict.set(str, dict.size + 1);
      const input = msg.slice(start, end - 1);
      answer.push(dict.get(input));
      start = end - 1;
    }
  }
  answer.push(dict.get(msg.slice(start, end - 1)));

  return answer;
}

 

마지막 문자열은 반복문 내에서 처리가 안 되므로 따로 추가해 줍니다.