문제

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

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

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

---

해결 과정

문제의 분류는 해시였지만 정렬을 이용해 풀었습니다.

1트(성공)

phone_book 리스트를 정렬한 후, 앞과 뒤를 비교해 뒤 문자열을 비교하는 방법으로 풀었습니다.

1. phone_book 리스트를 오름차순 정렬합니다.
2. phone_book 리스트의 다음 문자열에 현재 문자열이 포함되어 있다면 False를 반환합니다(어떤 번호가 다른 번호의 접두어인 경우).
3. len(phone_book)-1 만큼 리스트를 전부 돌면 True를 반환합니다(접두어가 없는 경우).

Code

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   

startswith(): 문자열이 지정된 접두사로 시작하는지 확인하는 파이썬 문자열 메서드

위 코드의 시간 복잡도는 O(nlogn) 입니다.

문제점

이 코드는 해시 테이블을 사용하는 해시 기반의 구현보다는 시간 복잡도가 크고, 메모리 사용량도 큽니다. 따라서 큰 입력에 대해서는 더 나은 성능을 발휘하지 못할 수 있습니다.

---

최적화 코드

Hash를 이용한 풀이

1. hash_map이라는 빈 딕셔너리를 만들고, phone_book에서 각 전화번호를 hash_map에 추가합니다.
2. 전화번호를 한 자리씩 읽으면서 prefix 문자열을 만듭니다.
3. prefix가 hash_map에 있고, 현재 전화번호와 같은 접두사가 아니면(prefix != phone_number), False를 반환합니다(어떤 번호가 다른 번호의 접두어인 경우).
4. 2, 3의 과정을 phone_book 리스트를 모두 돌 때 까지 반복합니다.
5. 모든 검사가 끝난 후, True를 반환합니다(접두어가 없는 경우).

Code

def solution(phone_book):
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1

    for phone_number in phone_book:
        prefix = ""
        for number in phone_number:
            prefix += number
            if prefix in hash_map and prefix != phone_number:
                return False
    return True

해시 기반의 이 구현 방법은 시간 복잡도가 O(N*K)입니다. for 루프가 두 번 중첩되어 있기 때문에, 최악의 경우에는 전체 전화번호부에서 모든 전화번호를 비교해야 하기 때문입니다.
그러나 해시 테이블을 사용하기 때문에 startswith() 메서드를 반복해서 호출하지 않아도 되므로, 앞서 소개한 startswith()를 사용하는 방법보다 더 빠릅니다.