Lv.2 전화번호 목록(해쉬)

코딩테스트 연습 - 전화번호 목록 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

해쉬의 근본이라고 할 수 있는 문제.

딕셔너리와 리스트의 시간복잡도 차이가 결정적인 역할을 하기에

이를 간파해야만 풀 수 있는 문제

 

1. 해쉬 코드

def solution(phone_book):
    # 기본값 설정
    answer = True
    hash_dic = {} 
    
    # dictionary의 임의 value값 정해주기
    for phone_number in phone_book:
        hash_dic[phone_number] = 1
        
    # 임의의 문자열 만들기 temp = "1" >> temp = "11" >> temp = "119"    
    for phone_number in phone_book:
        temp = ""
        for number in phone_number: 
            temp += number
            # 접두사가 되는지 검사해보고 있으면 False
            if temp in hash_dic and temp != phone_number:
                answer = False
    return answer

 

2. startswith 함수

'접두사'라는 단어가 나오면 바로 이 함수를 떠올려주면 편안하다.

# 다른 사람의 풀이

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

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