프로그래머스 전화번호 목록 JS

프론트엔드 퍼즐러·2023년 10월 3일

해시 문제들

목록 보기

2/4

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1

앞에서 설명한 예와 같습니다.

입출력 예 #2

한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3

첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

풀이

이 문제는 2가지 방법으로 해시 테이블과 정렬을 이용하여 풀 수 있습니다.

해시 테이블

해시 테이블을 이용하는 방법은 해시 테이블을 선언하고, 배열의 요소를 해시 테이블에 넣은 다음, 배열을 다시 반복하면서 배열의 요소의 길이만큼 자르고, 자른 문자열이 해시 테이블 안에 존재하면 바로 false를 return 해주는 방식 입니다. 코드는 아래와 같습니다.

  const hashTable = {};

// 요소를 해시 테이블에 저장한다.
  for (const number of phone_book) {
    hashTable[number] = true;
  };

  for (const number of phone_book) {
    for (let i = 1; i < number.length; i++) {
      const prefix = number.substring(0, i);
      if (hashTable[prefix]) return false;  
    };
  };

// 전부 통과했다면 true를 반환한다.
  return true;

정렬

정렬을 이용한 방법으로는 우선, 문자열 순서대로 배열을 정렬한 후,
Array.some()을 이용하여 이전 배열의 요소가 다음에 존재하는지 여부를 확인 후 boolean 값을 return 하면 됩니다. 코드는 다음과 같습니다.

phone_book.sort();

// some은 배열의 요소중 콜백함수의 판별식을 전부 통과하는지 검사한다.
// 통과하면 true, 실패하면 false이기 때문에 반대로 retrun 해 준다.
const isPrefix = phone_book.some((book,idx)=>{
    return phone_book[idx+1]?.startsWith(book);
})


return !isPrefix

속도 비교

코드상으로만 봤을 때, 해시 테이블은 기본 for문이 1번 2중 for문이 1번 그리고 문자열을 잘라야 하는 slice() 까지 쓰였고, 정렬을 이용하는 것은 처음 sort() 함수를 1번 쓰고 some()을 이용하여 다시한번 배열을 순회하기 때문에 해시 테이블 보다는 정렬을 이용한 방법이 더 효율성이 좋아 보입니다.

프로그래머스에서 제공하는 테스트 케이스로 비교해 봤을 때 효율성 테스트 3번을 기준으로 비교해 보았습니다.