[프로그래머스] 전화번호 목록 - ( 해쉬 / dict가, list보다 빠르다 )

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한 사항 phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들어있지 않습니다.

 

 

풀이

def solution(phone_book):
    answer = True
    phone_book.sort(key=lambda x:len(x)) # 길이순으로 정렬
    
    for i in range(len(phone_book)):
        num = phone_book[i]    # 찾을 값
        arr = phone_book[i+1:] # 
        
        for j in arr:
            if num == j[:len(num)]: # 앞부분 길이만큼 숫자가 동일 판단
                answer = False # 하나라도 있다면 종료
                break
            
    return answer

이렇게 작성했더니, 테스트 케이스틑 다 통과했지만 효율성 테스트에서 시간초과했다.

dict()을 사용해서 시간초과를 해결할 수 있을 것 같긴했지만, hash에 대한 이해가 없었기 때문에 개념 공부 겸 다른 사람의 코드를 참고해봤다.

 

 

def solution(phone_book): 

    # 1.Hash map생성
    hash_map = {} 
    for numbers in phone_book: 
        hash_map[numbers] = 1 

    # 2.접두어가 Hash map에 존재하는지 찾기 
    for numbers in phone_book: 
        arr = "" 
        for number in numbers: 
            arr += number  # 글자를 하나씩 더하면서 hash_map에 있는지 확인

            # 3. 본인 자체일 경우는 제외
            if arr in hash_map and arr != numbers:       
                return False          

    return True

사실 hash는 개념적인 것이고, dict()을 이용하던 방식과 동일하다.

리스트는 하나씩 접근, dict는 검색해서 한번에 접근 이라고 하지만,

솔직히 dict의 접근방식이 직관적으로 이해되진 않는다.

 

dict의 key 값에 접근하는 것도 결국 리스트처럼 하나씩 접근하는 것일 텐데, low level에서 접근하는 거라 빠른 것인지 좀 더 알아봐야할 것 같다. 

 

 

출처

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스