프로그래머스 - Lv.2 전화번호 목록 (해시) JS

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

 

해당 문제는 주어진 배열에서 특정 단어가 다른 단어에 대해 '접두어'로 쓸 수 있을 때 false, 접

두어로 쓸 수 있는 단어가 없을 때는 true를 반환하는 문제다.

문제 자체는 간단해 보이나 주어지는 배열의 길이가 백만이기 때문에 시간 복잡도에 의한 실패에 유의해야 한다.

 

내가 생각한 방식은 다음과 같다. 

 

먼저 해시로 활용할 객체를 만든다.

이후 길이가 긴 단어가 짧은 단어의 접두어가 될 수는 없으므로 길이가 짧은 순으로 정렬한 배열을 만든다.

정렬한 배열은 인덱스 순으로 해시 테이블에 추가하는 과정을 거치는데,

이때 반복문을 통해 앞에서부터 한글자씩 가져와 해당 단어가 이미 해시 테이블에 존재하지 않는지 검증한다.

(예를 들어, ace라는 단어가 있을 때, 'a, ac, ace'를 검증)

이때 해당 단어가 존재할 경우 false를 리턴하고, 모든 경우에서 접두어가 존재하지 않을 경우 true를 리턴한다.

 

작성한 소스 코드는 다음과 같다.

function solution(phone_book) {
  // 배열 정렬
  const sorted = phone_book.sort((a,b)=> a.length - b.length)
  // 테이블 생성
  const table = {}
  
  for(let i = 0 ; i < sorted.length ; i ++) {
    const str = sorted[i]
    for(let j = 0 ; j < sorted[i].length ; j ++) {
      // 단어를 앞에서 부터 잘라 
      const piece = str.slice(0,j+1)
      // 해시 테이블에 존재하는지 검증하고 만약 존재한다면 false 리턴 후 종료
      if(table[piece]) return false
    }
    // 잘랐던 모든 단어가 테이블 미존재 시 테이블에 단어 추가
    table[str] = true
  }
  // 모든 경우 통과 시 true 리턴 후 종료
  return true
}