[프로그래머스] 전화번호 목록 (해시를 이용한 풀이) (Python)

문제 설명

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

• 구조대: 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

문제풀이

해시 카테고리 내의 문제이며, 이 문제를 계기로 해시 알고리즘의 개념을 알게 되었다. 같은 값을 가지는 전화번호가 없기에 해시 알고리즘을 이용하여 풀기에 적합한 문제인가보다.

해싱: 키에 대한 해시값을 구하는 과정
해시 알고리즘: key-value를 이용하여 빠르게 검색이 가능하도록 하는 알고리즘.

• 키에 대한 해시값을 사용하여 값을 저장하고 key-value 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array이다.
• 해시값 자체를 index로 사용하기 때문에 평균 시간복잡도가 O(1) 로 매우 빠르다는 것이 장점이다.

앞선 풀이에서 정렬을 이용해서 풀었다면 이번에는 해시를 이용한 정석적인 방법을 통해 풀었다. 정렬을 이용했을 때의 효율성이 더 떨어질 거라 생각했는데 오히려 정렬을 이용한 풀이의 효율성이 더 좋게 나왔다. 왜지...?

1. 정렬

2. 해시

def solution(phone_book):
    hashmap = {}
    for phone in phone_book:
        hashmap[phone] = 1
    for phone in phone_book:
        text = ''
        for number in phone:
            text += number
            if text in hashmap and text != phone:
                
                return False
    
    return True

문제 풀러 가기!👇

전화번호 목록