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

✍️문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

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

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

제한 사항

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

---

조건으로 얻을 수 있는 정보

1. 배열의 길이가 `10^6` 이므로, 시간복잡도 `O(n x logn)`이 되도록 구현하여야 1초(10^8) 내에 실행 가능

2. `O(n^2)` 방법은 시간 내에 처리 불가능하지만, 시간이 부족하면 이를 채택 (실전)

 

1️⃣ Brute False

누구나 가장 먼저 생각나는 방법으로, 각 phone_number를 순회하면서 해당 번호를 접두어로 사용하고 있는 phone_number가 있는지 판단하는 방법이다.

 

- 최소한의 최적화를 위해, 비교하는 두 phone_number를 문자열이 아닌 숫자로 변환하여 비교하였다.

is_jupdo : 문자열 비교

is_jupdo2 : 숫자 비

// #시도1. Brute false 문자열 비교, 시간초과
function is_jupdo(target, diff) {
  const target_len = target.length;

  for (let i = 0; i < target_len; i++) {
    if (target[i] !== diff[i]) {
      return false;
    }
  }
  return true;
}

// #시도2. Brute False 숫자 비교, 시간초과
function is_jupdo2(target, diff, power_10) {
  const target_len = target.length;
  const diff_len = diff.length;

  if (Math.floor(diff / power_10[diff_len - target_len]) - target === 0) {
    return true;
  }
  return false;
}
function solution(phone_book) {
  const len = phone_book.length;
  const power_10 = [1];

  // 10의 거듭제곱 값 넣기
  for (let i = 1; i <= 20; i++) {
    power_10[i] = power_10[i - 1] * 10;
  }

  phone_book.sort((a, b) => a.length - b.length);

  for (let i = 0; i < len - 1; i++) {
    const target = phone_book[i];
    for (let j = i + 1; j < len; j++) {
      const diff = phone_book[j];
      // Compare
      if (is_jupdo2(target, diff, power_10)) {
        return false;
      }
    }
  }
  return true;
}

 

효율성 테케 실행 결과 역시나 실패

 

2️⃣Hash Table

1. phone_number 값을 객체 (Hash Table)에 저장한다. (아래 그림 참고)

2. 각 phone_number를 순회하며, 생성가능한 모든 접두어가 객체(Hash Table)에 존재하는지 확인한다.

Hash Table 구조

// 시도3: Hash Table만들기
function solution(phone_book) {
  const table = {};
  for (const phone of phone_book) {
    table[phone] = true;
  }

  for (const phone of phone_book) {
    const len = phone.length;
    for (let i = 1; i < len; i++) {
      const substr = phone.substring(0, i);
      if (table[substr] === true) {
        return false;
      }
    }
  }

  return true;
}

 

효율성 테케 실행 결과 성공

 

---

분석

1️⃣Brute False

• solution 함수에서는 전화번호를 길이 순으로 정렬한 후, 각 번호와 그 다음 번호들 간의 비교를 반복한다.
• 여기서 이중 반복문을 사용하므로, 시간 복잡도는 최악의 경우 O(n^2)이다.
• 또한, is_jupdo 호출은 두 문자열의 길이에 비례하여 O(m) 시간이 소요되며, 이는 두 문자열 길이의 최대값에 의해 결정된다.
• 따라서 전체 시간 복잡도는 `O(n^2×m)`로, 전화번호의 수가 많거나 각 번호의 길이가 길면 성능이 최악이다.

2️⃣Hash Table

• 해시 테이블에 각 전화번호를 저장한 후, 각 전화번호의 접두사가 테이블에 있는지 확인한다. (O(n))
• 각 phone_number의 길이-1 만큼 hash table에 접두어가 있는지 확인한다. (O(m))
• 따라서, 이 방법의 시간 복잡도는 `O(n×m)`로, n은 전화번호 개수이고, m은 각 전화번호의 길이이다.