[JS] 프로그래머스 / 해시 / 전화번호 목록

문제

프로그래머스

핵심 아이디어

• 전화번호 목록을 저장하기 위해 phone_book 배열의 각 전화번호를 키로 가지는 해시 테이블인 phoneMap을 생성한다. 해시를 사용하여 전화번호 검색을 O(1) 시간 복잡도로 수행할 수 있다.
• 각 전화번호에 대해 1자리부터 시작하여 마지막 자리 전까지의 모든 접두사를 생성하고, 해당 접두사가 phoneMap에 존재하는지 확인한다.
• 만약 접두사가 phoneMap에 존재한다면, 해당 전화번호가 다른 전화번호의 접두사임을 의미하므로 false를 반환한다.
• 모든 접두사 검사가 끝났다면, 모든 전화번호에 대해 접두사가 발견되지 않으면 true를 반환하여 모든 전화번호가 서로 접두사 관계에 있지 않음을 보장한다.

정답

function solution(phone_book) {
  const phoneMap = {};

  for (const phone_number of phone_book) {
    phoneMap[phone_number] = true;
  }

  for (const phone_number of phone_book) {
    for (let i = 1; i < phone_number.length; i++) {
      const prefix = phone_number.slice(0, i);

      if (phoneMap[prefix]) {
        return false;
      }
    }
  }

  return true;
}