압축

문제 요약

메시지를 압축해야 하는데 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

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

내가 푼 풀이

처음에는 그냥 객체 형태로 풀어야지 생각하고 문제를 풀다보니 재귀형태로 풀어야 하는구나 라는 것을 깨닫고 문제를 풀게 되었다.
제출하니 단번에 성공할수 있었다. map 객체로 문제를 풀었을때 성능이 더좋지 않을까 ? 생각하여 map객체를 이용하여 문제를 풀었는데 확실히 성능 측면에서 좋은 효과를 거둘수 있었다.

다음은 map객체로 푼 나의 풀이이다.

function solution(msg) {
    var answer = [];
    let arr = msg.split('').reverse();
    let alphabet = 'abcdefghijklmnopqrstuvwxyz'.toUpperCase().split('')
    
    let dictionary  = new Map()
    alphabet.map((alpha,i)=>dictionary.set(alpha,i+1));
  
  function addDictionary(string){

    let nextWord = arr.pop();
    if(!nextWord){
      // return dictionary[string];
      return dictionary.get(string);
    }
    let word = string+nextWord

    if(dictionary.has(word)){
      return addDictionary(word);
      
    }else{
      arr.push(nextWord);
      dictionary.set(word,dictionary.size+1)
     
      return dictionary.get(string);
    }
  }
  
  while(arr.length){
  
    let target = arr.pop();

    let num = addDictionary(target);
    answer.push(num)
  }
    return answer;
}

객체 형태와 map 객체 성능 비교

코드는 같고 map객체, obj객체 형태만 다른 것으로 측정했다.

1. 객체 형태 성능 값
   

2. map 객체
   코드는 내가 푼 풀이에 있다.

앞자리가 0. 대로 훨씬 빠르다.
나름 처음 푼걸로 성공해서 뿌듯하다.