[Hash] 전화번호 목록 - 프로그래머스

https://www.notion.so/ac6d6c63a1aa4c3a91f503f6ca7bd77a

전화번호 목록 [완료]

 

내 풀이

나 같은 경우는 사실 정말 단순하게 O(n^2)로 풀었다ㅠㅠ 이 문제를 n^2 알고리즘으로 푸는 건 좋은 방향은 아닌 것 같다

def solution(phone_book):
    phone_book = sorted(phone_book, key=lambda x : len(x))
    for i in range(len(phone_book)) : 
        for j in phone_book[i+1:] : 
            if phone_book[i] in j : 
                if phone_book[i][:len(phone_book[i])] == j[:len(phone_book[i])] : 
                    answer = False
                    return answer
    answer = True
    return answer

공부할 때 참고하면 좋을 다른 사람 풀이를 참고해보자

 

1) O(n) 풀이, zip을 사용

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

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

 

2) Hash의 논리 직접 구현

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

3) 정규 패턴식 사용

import re
def solution(phoneBook):

    for b in phoneBook:
        p = re.compile("^"+b)
        for b2 in phoneBook:
            if b != b2 and p.match(b2):
                return False
    return True