[프로그래머스-해시] 전화번호 목록

 

 

 

문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

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

 

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

 

입출력 예

 

 

풀이1. 시간 초과 

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)):
        i_len = len(phone_book[i])
        for j in range(i+1,len(phone_book)):
            if phone_book[j][:i_len] == phone_book[i]:
                return False
    return True

 

1. 전화번호 정렬: 먼저 phone_book을 사전순으로 정렬한다. 정렬을 하면, 접두어 관계에 있는 전화번호들이 서로 인접하게 위치하게 된다. 예를 들어, ["123", "1235", "567", "88"]와 같은 목록은 정렬 후 ["123", "1235", "567", "88"]가 된다.
    
    
2. 접두어 확인: 각 전화번호 phone_book[i]를 기준으로, 그 다음 전화번호들 phone_book[j]가 접두어 관계에 있는지 확인한다.
   • phone_book[j][:i_len] == phone_book[i] 조건문을 통해 phone_book[j]의 처음 i_len 길이 부분이 phone_book[i]와 같은지 검사
   • 만약 같다면 phone_book[i]가 phone_book[j]의 접두어가 되므로, False를 반환
   • 만약 모든 번호를 비교한 후에도 접두어 관계가 없으면 True를 반환

 

이 코드는 전화번호부를 정렬하는 데 O(n log n) 시간이 소요되며, 두 개의 중첩 반복문이 있으므로 최악의 경우 O(n^2)에 가까운 시간복잡도를 가질 수 있다.

 

 

 

 

풀이2. 

def solution(phone_book):
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return True

 

1. 전화번호 정렬: phone_book을 사전순으로 정렬한다. 
2. 접두어 확인: phone_book[i]와 phone_book[i+1]을 비교하여, phone_book[i]가 phone_book[i+1]의 접두어인지 확인한다.
   • phone_book[i + 1].startswith(phone_book[i])는 phone_book[i + 1]이 phone_book[i]로 시작하는지 검사한다.
   • 접두어 관계가 있다면 False를 반환한다.
   • 반복문이 끝날 때까지 접두어가 발견되지 않으면 True를 반환한다.

전화번호 목록을 정렬하는 데 O(n log n) 시간이 걸리며, 인접한 요소만 비교하기 때문에 비교 과정의 시간복잡도는 O(n)이다.

따라서 전체 시간복잡도는 O(n log n)으로 효율적이다.