전화번호 목록

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

프로그래머스

 

 

I. 문제 개요

모든 접두어 조합을 파악하고, 주어진 전화번호의 접두어가 앞서 파악한 조합에 있는 지 판별해야 한다.

 

접두어 조합은 O(n)으로 파악할 수 있지만, 알아낸 접두어 조합 안에서 탐색하는 것이 관건이다.

 

순차적으로 탐색할 경우, 최종적으로 O(n^2) 만큼의 시간복잡도를 소모하게 된다.

 

그 이유는 조합 형성에 더불어, 탐색에 추가적으로 O(n)의 시간복잡도를 소모하기 때문이다.

 

따라서, 시간복잡도 O(1) 안에 탐색할 수 있는 자료 구조를 활용해야 한다. 

 

여기서는 파이썬을 사용하므로, O(1)안에 탐색할 수 있는 set을 활용할 계획이다.

 

II. 알고리즘 및 풀이

1. 초기화 및 탐색 준비

ans = True
dct = set()   # set 활용 -> 탐색 시 O(1) 시간복잡도 확보

for p in phone_book:
    dct.add(p)  # set에 전화번호 넣기

 

set을 선언하고, 여기에 주어진 전화번호들을 넣는다.

 

한 전화번호가 다른 전화번호의 접두어일 수도 있기 때문이다.

 

2. 접두어 탐색

for p in phone_book:
    header = ''      # 접두어 초기화
    for n in p:
        header += n  # 접두어 생성
        if header in dct and header != p:  # 접두어가 주어진 전화번호 중 하나이면
            ans = False   
            return ans

return ans

 

먼저 각 전화번호마다 가능한 접두어를 생성한다.

 

만약 생성한 접두어와 같은 전화번호를 찾으면, ans의 값을 False로 바꾸고 이를 반환한다.

 

모든 번호를 탐색했다면, 한 번호가 다른 번호의 접두어가 되는 경우를 못찾았으므로, ans를 그대로 반환한다.

 

 

III. 전체 코드

# A. Set 활용
def solution(phone_book):
    # 1. 초기화 및 탐색 준비
    ans = True
    dct = set()   # set 활용 -> 탐색 시 O(1) 시간복잡도 확보

    for p in phone_book:
        dct.add(p)  # set에 전화번호 넣기
    
    # 2. 접두어 탐색
    for p in phone_book:
        header = ''      # 접두어 초기화
        for n in p:
            header += n  # 접두어 생성
            if header in dct and header != p:  # 접두어가 주어진 전화번호 중 하나이면
                ans = False   
                return ans

    return ans

 

IV. 채점 결과