해시 맵 자료구조 풀이#2

해시 맵 문제 풀이(프로그래머스: 전화번호 목록)

https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=javascript

문제 설명

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

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

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

제한 사항

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

---

풀이

• 주어진 배열을 이용해서 해시 맵의 키값에 각 값을 담고 value에는 임의의 값을 넣어 준다.
• 주어진 배열을 다시 반복문으로 돌리고, 각 문자열의 길이만큼 반복문을 돌려서 slice를 이용해 문자를 자른다.
• 자른 문자가 접두사로 사용되고 있는지 맵에서 찾는다.
• 만약 키가 존재한다면 false를 반환해 준다.

function solution(phone_book) {
  var answer = true;

  let map = new Map();

  // 모든 전화번호를 맵에 저장
  for (let i = 0; i < phone_book.length; i++) {
    map.set(phone_book[i], true);
  }

  // 각 전화번호에 대해 모든 접두어를 확인
  for (let number of phone_book) {
    for (let i = 1; i < number.length; i++) {
      const prefix = number.slice(0, i);
      if (map.has(prefix)) {
        return false;
      }
    }
  }

  return answer;
}

---

풀면서 든 생각 및 다른 점

: 맵을 사용하지 않고 배열을 사용해도 비슷하게 풀 수 있을 것 같다는 생각이 들었다.

& 찾아본 결과

• 배열을 사용하면 조금 더 직관적으로 풀이를 만들 수 있다.
• 하지만 이번 문제의 배열 풀이에는 정렬이 필요하기 때문에 큰 입력에 대해서는 비효율적인 결과가 나올 수 있습니다.

& 결론

• 그래서 해시 테이블 방식이 정렬 없이 접두어를 빠르게 찾을 수 있어서 대규모 입력에서 성능이 더 좋기 때문에, 해시 테이블을 이용한 풀이가 조금 더 효율적입니다.

마무리

• 이번 문제의 카테고리가 해시였기 때문에 익숙한 배열로 풀이를 생각해 보려다가 해시로 먼저 문제를 풀었습니다.
• 그리고 배열로 풀었을 경우의 차이를 찾아보면서 이유를 알게 됐는데, 아직 무엇이 더 좋은 방법인지 한 번에 판단되지는 않아서 조금 더 데이터를 쌓아 나가야 할 것 같습니다.