[programmers] 압축 (in JS)

문제

압축 - 2018 KAKAO BLIND RECRUITMENT

접근

• A부터 Z까지 문자를 key, 그 index를 value로 하여 Map을 초기화한다.

const initDictionary = (dict) => {
  for (let i = "A".charCodeAt(0); i <= "Z".charCodeAt(0); i++) {
    dict.set(String.fromCharCode(i), dict.size + 1);
  }
};

• msg가 비어있는 문자열이 아닐 때까지 다음을 반복한다.
• 가장 긴 문자열을 찾는다.
  - msg의 첫 번째 문자부터 마지막 문자를 덧붙여가며, 덧붙여진 문자가 사전에 있는 가장 긴 문자열을 찾는다.
• 가장 긴 문자열에서 다음 문자열이 존재한다면, 사전에 등록한다.
• msg에서 가장 긴 문자열은 이미 처리되었으므로, 제외시킨다.

복잡도

• 공간 복잡도 : O(N)
  - 최악의 경우, 모두 사전에서 찾을 수 없으므로, answer은 msg의 길이만큼의 배열이 필요하다.
• 시간 복잡도 : O(N)
  - msg를 한 번 순회하여 알 수 있다.

알게된 점

• javascript에서 문자의 유니코드를 찾는 메서드는 String.prototype.charCodeAt()이다.
• javascript에서 유니코드의 문자를 반환하는 메서드는 String.fromCharCode() 이다.

코드

const initDictionary = (dict) => {
  for (let i = "A".charCodeAt(0); i <= "Z".charCodeAt(0); i++) {
    dict.set(String.fromCharCode(i), dict.size + 1);
  }
};

const findLongestMsg = (msg, dict) => {
  let longestMsg = "";
  for (const alpha of msg) {
    if (!dict.has(longestMsg + alpha)) {
      break;
    }
    longestMsg += alpha;
  }
  return longestMsg;
};

const enrollNewWord = (word, dict) => {
  dict.set(word, dict.size + 1);
};

function solution(msg) {
  const answer = [];
  const dict = new Map();
  initDictionary(dict);
  while (!!msg.length) {
    const longestMsg = findLongestMsg(msg, dict);
    answer.push(dict.get(longestMsg));
    if (longestMsg.length < msg.length) {
      enrollNewWord(longestMsg + msg[longestMsg.length], dict);
    }
    msg = msg.slice(longestMsg.length);
  }
  return answer;
}