전화번호 목록 (lv2)

문제 설명

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

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

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

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.

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

---

  해싱으로 접근해야 한다길래 그만 너무 어렵게(?) 풀어버린것 같다. 아이디어는, 다음과 같은 모양을 만들어 같은 접두어를 가진 번호끼리 묶어주려는 것이었다.

 즉 '전화번호'의 문자별로 딕셔너리를 만든다는 방법이다. '전화 번호'에 대한 중복 검사를 피하고 싶은 마음으로 도전한 방법이었으나, 막상 해놓고 생각해보니 지나치게 깊은 딕셔너리를 만들어 버리는 방법이다. 해시의 강점인 빠른 검색 속도 역시 이딴 방법으론 보장되지 않으니, 이건 해시로 풀었다고 볼 수 도 없다. '전화번호'의 길이가 최대 20이니까, 최악의 경우 깊이가 20인 무시무시한 딕셔너리가 만들어지는 셈이다. 다시는 이런 방법으로 접근하지 않으리...

import sys
sys.setrecursionlimit(10**7)

answer = True

def hashing(li,cnt):
    global answer
    if not answer:
        return
    if len(li) <= 1:
        return li[0]
    table = dict()
    for num in li:
        try:
            if not table.get(num[cnt]):
                table[num[cnt]] = [num]
            else:
                table[num[cnt]].append(num)
        except IndexError:
            table['.'] = [num]
    for i in table.keys():
        if i == '.' and len(table.keys()) > 1:
            answer = False
        table[i] = hashing(table[i],cnt+1)
    return table

def solution(phone_book):
    hashing(phone_book,0)
    return answer

 다음 방법은 위 방법보다 훨씬 정석적이며, set의 hash table 특성을 적극적으로 활용하고 있다. 아래 링크는 set과 dict의 특성을 잘 설명해주고 있다.

파이썬 set의 데이터구조부터 hashtable까지(갑분 C 등장) (velog.io)

파이썬 set의 데이터구조부터 hashtable까지(갑분 C 등장)

  phone_book을 순회하면서, 각 전화번호의 문자를 다시 순회하며 해당 문자의 접두어가 존재하는지 확인하는 풀이법이다.

def solution(phone_book):
    hash_map = set(phone_book)
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                return False
    return True

 마지막으로 가장 빠른 방법인 파이썬에서 기본으로 제공되는 startswith 메서드를 활용한 방법이다.

코딩벌레 :: [Python] 파이썬 특정문자 찾기(find,startswith,endswith) (tistory.com)

[Python] 파이썬 특정문자 찾기(find,startswith,endswith)

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

 여러모로 억울한 문제였다...