[Programmers] 해시 - 전화번호 목록

본 문제를 풀 때, 해시 카테고리에 있었으므로 먼저 딕셔너리를 사용해야 한다는 것은 인지하고 시작하였다.

먼저, 문제를 읽어보면 한 번호가 다른 번호의 접두어인 경우가 있다면 false를 반환하고, 아니라면 true를 반환하면 된다.

조금 더 쉽게 생각하면, 문제에서 주어진 구조대 번호는 119이고 지영석의 번호는 11 9552 4421이므로 지영석의 번호는 구조대의 119와 일치한다. 따라서 false를 반환해야 하는 것이다.

 

먼저 전화번호부를 딕셔너리로 새로 만들어주자.

딕셔너리의 경우 key값을 안다는 가정하에 자료 검색에 대한 시간 복잡도는 상수 시간 O(1)이 걸리므로 아주 빠르게 접근이 가능하다.

여기서 key에 전화번호를, value는 임의의 값을 아무거나 초기화하면 된다.

전화번호라서 value에 값을 넣으려고 할 수도 있지만 딕셔너리에서 검색의 시간 복잡도가 O(1)이 되기 위해서는 항상 키 값을 안다는 가정이 있어야 한다는 것을 명심하자.

phone_numbers = {}
for i in range(len(phone_book)):
    phone_numbers[phone_book[i]] = 1

 

여기까지 했다면, {'119': 1, '97674223': 1, '1195524421': 1}과 같이 딕셔너리 형태로 전화번호부가 만들어졌다.

 

이제 생각을 해 보자, 1195524421 이 번호에서 119가 있는지 없는지 어떻게 판단할 수 있을까?

접두어를 찾아야 하기 때문에 일단 앞에 글자를 잘라야 한다는 것까지는 생각할 수 있다. 그렇다면 얼마나 잘라야 할까?

현재 예시의 경우는 119가 가장 짧은 경우인데, 이때 운이 좋게 1195524421이 119를 접두어로 사용하는 것을 쉽게 볼 수 있었다.

그런데 만약 14224, 5818231, 1929581823100이라면 어떨까? 이 경우에서는 가장 짧은 키의 길이가 접두어가 아니라는 것을 확인할 수 있다.

 

즉, 얼마나 잘라야 하는지 모르기 때문에 가능한 모든 경우를 다 잘라 봐야 한다.

가령 119라면 1, 11, 119와 같이,

97674223이라면 9, 97, 976, 9767, 97674, 976742, 9767422, 97674223과 같은 형식으로 자르는 경우를 생각할 수 있다.

슬라이싱을 활용하여 키 값을 각각 다 잘라서 보자.

for key, value in phone_numbers.items():
        for i in range(len(key)):
            prefix = key[:i+1]

 

이제 prefix 값이 실제 전화번호부에 포함되어 있는지 확인하면 되는데, 119를 119까지 자르면 자기 자신도 포함하기 때문에 항상 포함한다고 나오게 된다.

따라서 자기 자신의 번호가 포함된 것을 검색하는 것을 방지하기 위해 자를 때, 다음과 같이 마지막 직전까지만 잘라야 한다.

for key, value in phone_numbers.items():
        for i in range(len(key)):
            prefix = key[:i]

 

여기까지 했다면 각 번호에 대해 아래와 같이 자를 것이라는 것을 생각할 수 있다.

#             119:    1, 11

#  97574221:    9, 97, 976, 9767, 97674, 976742, 9767422

# 119552442:    1, 11, 119, 1195, 11955, 119552, 1195524, 11955244, 119552442

 

그러면 각각 잘린 접두어들이 실제 전화번호부에 있는지 in 키워드와 if문으로 판단하면 끝나는 문제이다.

주의할 것은 in으로 포함 관계만 확인하면 되기 때문에 기존 문제에서 주어진 배열인 phone_book 안에 있는지 확인할 수도 있는데, 이렇게 되면 조회는 정상적으로 잘 되지만 배열 안에서의 검색은 시간 복잡도가 O(N)이기 때문에 본 문제의 효율성 검사를 통과할 수 없다.

그러나 같은 in이라도 딕셔너리 안에서의 in 키워드는 키와 일치하는 것이 있는지 없는지 O(1)의 시간 복잡도로 조회할 수 있기 때문에 아주 빠르게 검색할 수 있고, 최종적으로 효율성 부분까지 고려하여 문제를 해결할 수 있다.

def solution(phone_book):
    answer = True
    phone_numbers = {}
    for i in range(len(phone_book)):
        phone_numbers[phone_book[i]] = 1
    
    for key, value in phone_numbers.items():
        for i in range(len(key)):
            prefix = key[:i]
            
            #if prefix in phone_book:
            if prefix in phone_numbers:
                answer = False
            
    return answer

 

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119

박준영 : 97 674 223

지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.

각 전화번호의 길이는 1 이상 20 이하입니다.

같은 전화번호가 중복해서 들어있지 않습니다.

 

입출력 예제

phone_book                                            return

["119", "97674223", "1195524421"]    false

["123","456","789"]                                true

["12","123","1235","567","88"]              false

 

입출력 예 설명

입출력 예 #1

앞에서 설명한 예와 같습니다.

 

입출력 예 #2 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

 

입출력 예 #3 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

최종 코드

def solution(phone_book):
    answer = True
    phone_numbers = {}
    for i in range(len(phone_book)):
        phone_numbers[phone_book[i]] = 1
    
    cnt = 0
    for key, value in phone_numbers.items():
        for i in range(len(key)):
            prefix = key[:i]
            
            #if prefix in phone_book: # 리스트로 하면 선형 탐색 O(N)
            if prefix in phone_numbers: # 딕셔너리로 하면 상수 시간 O(1)
                answer = False
            
    return answer