해시 맵 자료구조 풀이#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);
  }

  // 2. 각 전화번호에 대해 모든 접두어를 확인
  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;
}

---

풀면서 든 생각 및 다른점

: 맵을 안쓰고 배열을 써도 비슷하게 풀 수 있을 것 같다는 생각이 들었다.

& 찾아본 결과

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

& 결론

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

마무리

• 이번 문제의 카테고리가 해시였기때문에, 익숙한 배열로 풀이를 생각해보려다가 해시로 먼저 문제를 풀었습니다.
• 그리고, 배열로 했을 경우에 대한 차이를 찾아보면서 , 이유를 알게 됐는데 아직 뭐가 더 좋은 방법일까라는 생각은 한 번에 안들어서 좀 더 데이터를 쌓아나가야할 것 같습니다.