🔎 압축

❓ 문제링크

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

📄 제출 코드

function solution(msg) {
  let Alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  let dictionary = {}
  var answer = [];
  for (let i = 0; i < 26; i++) {
    dictionary[Alpha[i]] = (i + 1);
  }

  let idx = 27;
  let cur = 0;
  while (msg[cur]) {
    let wc = msg[cur];
    // 다 끝났을때
    if (cur == msg.length - 1) {
      answer.push(dictionary[wc]);
      break;
    }
    for (let i = cur + 1; i < msg.length; i++) {
      wc += msg[i];
      console.log(`wc : ${wc}`)
      cur++;

      if (dictionary[wc] === undefined) {
        dictionary[wc] = idx;
        let tmp = wc.slice(0,-1);
        // console.log(`tmp : ${tmp}`)
        answer.push(dictionary[tmp]);
        idx++;
        break;
      }
      // 남은거
      if (i === msg.length -1) {
        answer.push(dictionary[wc]);
        cur++;
      }
    }
  }
  // console.log(dictionary);
  return answer;
}
let msg = 'KAKAO';
console.log(solution(msg));

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

구현하는 문제라서 차근차근 구현해나갔다.
먼저 알파벳A-Z를 dictionary에 key,value로 세팅한다. ex) A: 1, B: 2, ...
구현을 하고 "KAKAO" 문자열을 통과하고, 채점하니 몇가지는 틀렸다고 나왔다.
하나하나 console로 확인해보니 이상한게 보였다.
그렇게 구현하다가 막혀서 결국 다른 사람의 코드를 참고했다.

시작점 cur = 0.
초기 wc = msg[cur]
만약 cur이 끝에 다다르면 마지막 wc의 값을 answer에 추가.
cur다음꺼부터 메세지 끝까지 반복하면서 answer를 찾는다.

wc에 그 다음 글자를 추가하고, dictionary에 없으면 dictionary에 wc를 추가하고, answer에 wc의 처음부터 끝에서 첫번째까지 자른 글자key의 값을 answer에 추가.
새로 추가했으니 idx는 증가시키고 다음으로 넘어간다.
반복하다가 끝에 도착하면 남은걸 추가해준다.

if (cur == msg.length - 1) {
  answer.push(dictionary[wc]);
  break;
}

이 부분은 "KAKAO"에서 마지막에 KAO를 저장하고, 남은 O처리.

if (i === msg.length -1) {
  answer.push(dictionary[wc]);
  cur++;
}

반복문 안의 이 부분은 "TOBEORNOTTOBEORTOBEORNOT" 에서 마지막에 OT 처리
두 개 테케로 비교하면 될거 같다.

📘 참고

https://kis6473.tistory.com/172