[Programmers] 전화번호 목록

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42577

해설

한 번호가 다른 번호의 접두어인 경우를 찾는 것이다. 그런데 구하는 방법이 한 번호가 다시 다른 번호의 접두어인지 확인하는 방법을 역으로 구한다. 역으로라는 의미는 접두어를 구하고 이 구한 접두어가 phone_book에 존재하는 지를 확인하는 것이다. 이때 한 번호의 접두어는 어려가지 경우가 있다. 한 번호의 접두어를 하나씩 구하고, 이렇게 구한 접두어가 기존 번호 리스트에 있는지 확인하면 된다. 이때 확인하는 방법을 구한 접두어 번호마다 다시 phone_book list에서 확인하면 O(n)의 시간복잡도를 갖고 n이 최대 1,000,000이므로 효율성이 좋지 않다.
예를 들면 "119"의 접두어는 "1", "11"가 있다. 그리고 이렇게 구한 접두어가 다시 phone_book에 있는지 확인하는 것이다. 그런데 phone_book은 list이므로 존재 여부를 확인하려면 O(n)의 시간복잡도를 갖는다. 그런데 phone_book의 원소 모두를 해시 자료구조에 저장해두고 이 저장한 해시 자료구조를 check_dict라고 하자. 그리고 접두어와 check_dict와의 비교를 통해 확인하면 O(1)로 시간복잡도를 낮출 수 있다. 키가 존재하는지 확인하는 방법을 파이썬에서 in 연산자를 활용하면 된다.(get()함수를 활용해 key 값을 확인하는 방법도 있다.

 

특정 값이 존재하는 지 찾기 위해서는 list가 아니라 hash 자료구조를 이용하는 것이 훨씬 유리하다. list는 순서가 있는 자료를 저장하는 자료구조이기 때문에 어떤 자료의 순서로 값을 찾을 때 유리하다. 하지만 찾고자하는 자료가 몇번째 순서인지는 모르고 자료의 이름만 알고 있을 때는 hash 자료구조를 사용하면 된다. 아래 시간초과 코드에서는 번호의 접두어를 각각 구할 때마다 list에서 자료가 존재하는지 찾고 있다. list에서 원하는 자료가 있는지 확인할 때 컴퓨터 내부에서는 반복문으로 0번 인덱스부터 n-1 인덱스의 원소마다 확인하는 로직이 수행된다.

이렇게 될 때 시간 복잡도는 phone_book의 자료 n이고 각각의 원소의 길이가 최대 20 이므로 20n마다 다시 n개의 자료에 접두어로 존재하는지 확인하면 O(n^2)의 시간복잡도를 계산할 수 있다. 그런데 리스트에 존재하는 원소를 hash 자료구조로 미리 구현해두고 확인하면 시간복잡도를 줄일 수 있다. 이렇게 구현한 코드의 시간복잡도를 계산하면 hash 자료구조를 만드는 시간은 n이 걸리고 다시 n개의 원소마다 접두어를 구하면 20n 이다. 그리고 20n에 대해 hash에 자료가 있는지 확인하면 20n*1이 걸린다. 그러므로 최종 시간복잡도는 O(21n)이고 빅오 표기법에 의해 O(n)이 걸린다. 리스트를 사용했을 때는 n^2이였던 코드가 해시를 미리 구현하고 계산했더니 n으로 시간복잡도가 줄어들었다.

 

 

 

시간 초과 코드

def solution(phone_book):

    for phone_number in phone_book:
        start_number = ""
        for number in phone_number:
            start_number += number

            if start_number != phone_number and start_number in phone_book:
                return False
    else:
        return True

코드

def solution(phone_book):
    check_dict = {}

    for phone_number in phone_book:
        check_dict[phone_number] = True

    for phone_number in phone_book:
        start_number = ""
        for number in phone_number:
            start_number += number

            if start_number != phone_number and start_number in check_dict:
                return False
    else:
        return True

def solution(phone_book):
    check_dict = {}

    for phone_number in phone_book:
        check_dict[phone_number] = True

    for phone_number in phone_book:
        start_number = ""
        for number in phone_number:
            start_number += number

            if start_number != phone_number:
                if check_dict.get(start_number) != None:
                    return False
    else:
        return True