전화번호 목록-파이썬(Python) [프로그래머스/코딩테스트 연습/Lv.2]

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=python3

프로그래머스

 

---

풀이

def solution(phone_book):
    prefix_set= set() # 접두어들의 집합
    for i in phone_book:
        for j in range(1,len(i)):
            prefix_set.add(i[:j]) # 가능한 모든 접두어들을 추가해준다.
    for i in phone_book:
        if i in prefix_set: # 특정 전화번호와 다른 전화번호의 접두어가 같을 경우
            return False
    return True

---

Tip

• 각 전화번호들마다 해당 전화번호가 다른 전화번호들의 접두사인지 확인하는 방법은 O(n^2)의 시간복잡도가 필요하다. 그런데 phone_book의 최대 크기가 1,000,000이므로 불가능하다. (시간 초과)
• 따라서 반복문을 돌면서 각 전화번호의 접두사들을 집합(prefix_set)에 넣은 뒤, 다시 반복문을 돌면서 각 전화번호가 집합에 존재하는지 확인하면 O(n*20(=최대 전화번호 길이))의 시간복잡도로 풀 수 있다.

 

• 추가로 아래와 같이 풀 수도 있다.

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

• 이 방법은 정렬을 이용한 방법으로 시간복잡도는 O(nlog(n))이다.
• 어떤 문자열 a가 문자열 b의 접두사이고 나머지 문자열들의 접두사가 아닐 경우, 정렬했을 때 a가 b 바로 앞에 있게 되므로, 그 점을 활용한 것이다.

---

TIL

• str1.startswith(str2): str2가 str1으로 시작하는지 확인하여 맞을 경우 True, 아닐 경우 False를 반환한다. (str2가 str1의 접두사인지 확인)
• zip(a,b)에서 a와 b의 길이가 다를 경우 더 짧은 쪽을 기준으로 길이가 결정된다.

a=[1,2,3]
b=[4,5]

for i,j in zip(a,b):
	print((i,j))
    
'''
결과:
(1,4)
(2,5)
'''