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

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

프로그래머스

문제 설명

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

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

 

풀이 (25)

원소 하나하나 배열의 모든 요소에 대해 includes() 메서드로 판별을 하면 효율성에서 떨어지겠구나 생각할 수 있다.

따라서 Map을 이용하여 전화번호의 앞부분이 존재하는지 탐색하면 된다.

 

문제의 예시를 보기로 설명을 하자면,

["119", "1195524421"] false

 

119를 map에 삽입할 때 배열 안에 "1", "11", "119"가 이미 존재하는지 확인을 하고 없다면 추가하는 방식으로 탐색하면 된다.

"1195524421"을 map에 삽일할 때는 "1", "11", "119"가 존재하는지 확인을 할 때 map에 이미 존재하는 것으로 확인 되므로 false를 반환하게 된다.

 

모든 전화번호에 대해서 탐색을 하여도 최대 1,000,000 * 20의 경우의 수에 지나지 않는다

 

주의할 점은 배열을 정렬을 한 뒤에 적용하여야 한다는 것이다.

["123", "12"] 를 예시로 

 

"123"이 이미 삽입되어 있는 상태에서 "1"과 "12"를 탐색하여도 존재하지 않지만,

정렬을 한 뒤에는 "12"가 이미 삽입 된 상태로 등록된 접두 번호를 찾아낼 수 있게 된다.

 

코드

// 어떤 번호가 다른 번호의 접두어인 경우 ? false : true

function solution(phones) {
  const phoneMap = new Map();

  // ["12", "1"] 과 같은 순서로는 접두번호를 판별할 수 없기 때문에 오름차순 정렬이 우선
  phones = phones.sort((a, b) => a - b);

  for (const phone of phones) {
    for (let i = 0; i < phone.length; i++) {
      //  앞부분을 자른 모양이 이미 포함되어 있다면 false ["12", "12999"] => 12999.slice(0,2)가 이미 포함
      if (phoneMap.has(phone.slice(0, i + 1))) {
        return false;
      }
    }
    phoneMap.set(phone, true);
  }

  return true;
}

console.log(solution(["123", "456", "789", "12"]));