프로그래머스: 전화번호 목록 (파이썬, hash, dictionary)

hash문제이다. 자바에서는 해시값을 사용하는 자료형이 hashmap이고 파이썬에서는 dictionary이다. 내가 푼 문제가 아닌건 블로그에 기록하지 않는데 풀이가 너무 좋아서 내 나름의 수정을 더해 코드와 깨달은 점을 올려본다.

 

전화번호부가 10^6이기에 완전탐색을 하면 시간복잡도가 O(n^2)이므로 10^12이 되어 시간초과가 날 것 같았다. 

따라서 처음에 푼 풀이는 비교하려는 수보다 큰 수일때만 접두사가 될 수 있다는 점, 비교하려는 수보다 값이 커지면 더 비교를 할 필요가 없다는 점을 이용해 반복문에 조건문을 추가하여 탐색을 중간에 멈추게 함으로써 시간복잡도를 nO(logn)으로 만들어 6*10^6으로 풀려고 시도했으나 보기좋게 마지막시도에서 계속 시간초과가 났다.

예를 들어 [121, 83, 5555, 1253] 이라는 배열이 있다면 5555는 83보다 길이가 기므로 접두사가 될 수 없다. 또한 121과 1253을 비교한다면 접두사가 아니므로 1253과 길이가 같으면서 앞3자리가 1253보다 큰 5555는 접두사가 될 수 없다. 

 

코드를 다양하게 시도해 보아도 계속 효율성 테스트4에서 시간초과가 났는데 질문하기의 다른 사람이 올려주신 코드를 통해 문제를 해결할 수 있었다.

def solution(phone_book):
    s = {}
    min_ = float('inf')
    for phone in phone_book:
        if len(phone) < min_:
            min_ = len(phone)

    for p in phone_book:
        for i in range(min_, len(p)):
            s[p[:i]] = 1

    for p in phone_book:
        if p in s:
            return False
    return True

출처: https://school.programmers.co.kr/questions/39655

 

IceBear님이 올려주신 코드인데 phone_book의 원소들을 1부터 각 원소의 길이만큼 slice하여 dictionary의 key에 넣어준다. 원 코드는 1부터 모두 쪼개지만 길이의 최소값을 찾는 코드를 추가해 dictionary에 key를 추가하는 횟수를 줄여 보았다.

이를 통해 메모리와 속도면에서 더 효율적으로 풀 수 있음을 볼 수 있었다. 

효율성 테스트 결과(좌: IceBear님의 원본코드, 우: 약간의 수정을 더한 코드)

이 풀이를 통해 두가지 중요한 점을 배웠다.

 

하나는 dictionary를 초기화할 때 꼭 key-value 모두 의미있는 값을 사용할 필요는 없다는 것이고

 

두번째는 파이썬의 dictionary에 포함 연산자 in을 쓰면 key값들에 있는지를 확인한다는 것이다.