[알고리즘]프로그래머스 - 2018 KAKAO BLIND RECRUITMENT [3차] 압축

문제 설명

 

제한사항

• 입력으로 영문 대문자로만 이뤄진 문자열 msg가 주어진다. msg의 길이는 1글자 이상, 1000글자 이하이다.
• 주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.

입출력 예

 

내가 푼 코드

function solution(msg) {
  var answer = [];
  const index = [];

  for (let i = 0; i < 26; i++) {
    index.push(String.fromCharCode(i + 65));
  }

  for (let i = 0; i < msg.length; i++) {
    let [w, c] = [msg[i], msg[i + 1]];

    while (index.includes(w)) {
      let message = w + c;
      if (index.includes(message)) {
        w += c;
        c = msg[++i + 1];
      } else {
        answer.push(index.indexOf(w) + 1);
        index.push(w + c);
        break;
      }
    }
  }

  return answer;
}

 

QnA

1. 알파벳 배열을 손쉽게 짤 수 있는 방법은 없는가?

 

기존 내 코드

  const index = [];

  for (let i = 0; i < 26; i++) {
    index.push(String.fromCharCode(i + 65));
  }

 

간결한 방법

const index = Array.from({ length: 26 }, (v, i) => String.fromCharCode(i + 65));

• 시간복잡도는 동일하나, 보기에 좀 더 간결하다.
• new Array() 는 빈 배열 또는 특정 길이의 배열을 만드는 데 사용되고
• Array.from() 은 매핑함수를 적용하는 옵션과 함께 반복 가능하거나 배열과 유사한 객체에서 배열을 만드는데 사용

 

내가 작성한 코드에서 좀 더 시간 복잡도 줄이는 방법은?

내가 작성한 코드의 시간 복잡도 : O(n(=msg.length) * m(동적으로 증가하는 index))

function solution(msg) {
    let answer = [];
    let dic = {};
    
 	for (let i = 0; i < 26; i++) {
        dic[String.fromCharCode(i + 65)] = i + 1;
    }
    
    let currentWord = '';
    let nextIndex = 27; // A-Z를 넘어서는 색인
    
    for (let i = 0; i < msg.length; i++) {
        currentWord += msg[i];
 
        if (!(currentWord in dic)) {
            answer.push(dic[currentWord.slice(0, -1)]); // 이전 단어의 색인을 결과에 추가
            dic[currentWord] = nextIndex++;             // 새 단어를 사전에 추가
            currentWord = msg[i];                       // currentWord 초기화
        }
    }
    
    if (currentWord) answer.push(dic[currentWord]);
    
    return answer;
}

 

• 해시 맵에서의 검색/추가는 평균적으로 O(1)임을 이용한 코드
• 시간 복잡도 O(n)