[LV2]전화번호 목록

[LV2]전화번호 목록 문제링크 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. www.programmer.co.kr

 

문제해설

 

이번 문제는 리스트를 통해서 모든 탐색을 하면 정확성을 만점을 받을 수 있지만 효율성에서 시간초과가 나오게 된다. 그렇기 때문에 해시(hash) 알고리즘을 사용해야하는데 파이썬은 딕셔너리가 이 역할을 한다.

def solution(phone_book):
    answer = True  
    hash={}#딕셔너리 선언
    for i in phone_book: #모든 전화번호를 (전화번호:0) 으로 설정
        hash[i]=0 
    for i in phone_book:
        tmp=''
        for j in i: #모든 원소를 탐색 하여 만약 접두사가 있다면 False를 return
            tmp+=j
            if tmp in hash and tmp!=i:
                answer=False
            
    return answer

 

문제 key point

 

• 모든 원소를 탐색하고 비교해야 하는 경우 해시 알고리즘을 사용하는게 더 효율적이다
• 파이썬에서는 딕셔너리가 해시 알고리즘 역할을 한다