전화번호 목록

Last updated Dec 14, 2022 Edit Source

• Lv 2
• Hash

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

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

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

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

입출력 예 #1
앞에서 설명한 예와 같습니다.

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def solution(phone_book):
    dic = {}

    for num in phone_book:
        if num[0] not in dic:
            dic[num[0]] = [num]
        else:
            dic[num[0]].append(num)

    for i in dic:
        dic[i].sort()

    for i in dic:
        if len(dic[i]) == 1:
            continue
        else:
            start = dic[i][0]
            area = len(start)
            for j in range(1, len(dic[i])):
                if start in dic[i][j][:area]:
                    return False
                else:
                    start = dic[i][j]
                    area = len(start)
    return True

Note

이 문제는 hash자료구조, 즉 파이썬 dictionary 자료구조를 이용해 풀 수 있다. 주어진 phone_book에서 각 번호의 첫째 글자를 hash에 key로 저장하고, 그 첫째 글자로 시작하는 모든 숫자들을 value에 리스트로 저장한다. 그리고 각 리스트를 정렬한 후, 인접한 것들끼리 비교하는 방식으로 문제를 해결했다. 이럴 경우 시간 복잡도는 $O(n * log(n))$가 된다.

1
2
3
4
5
6
7

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

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

Note

이 코드는 이전 코드의 보다 간결하고 효율적인 구현이다. 먼저 내장된 정렬 기능을 사용하여 전화 번호의 입력 목록을 정렬한다. 그런 다음 zip 을 사용하여 각 전화 번호를 목록의 다음 전화 번호와 페어링하고 for 루프를 사용하여 이러한 쌍을 확인하는 작업을 반복한다. 각 전화 번호 쌍에 대해 이 코드는 starts with 메서드를 사용하여 두 번째 전화 번호가 첫 번째 전화 번호의 접두사인지 확인한다. 한 전화 번호가 다른 전화 번호의 접두사임을 발견하면 즉시 False를 반환한다. 접두사를 찾지 않고 모든 쌍을 반복하는 것을 마치면 True를 반환한다. 이 코드는 이전 코드의 해당 루프보다 효율적인 내장 정렬(sorted) 및 zip 함수를 사용하기 때문에 이전 구현보다 효율적입니다. 또한, 이전 코드에는 세 개의 별도 루프가 있는 반면, 여기서는 전화 번호 목록을 한 번만 루프하면 됩니다. 따라서 이 코드의 시간 복잡도는 $O(n * log(n))$이며, 여기서 n은 입력 목록에 있는 전화 번호의 수이고, 이는 이전 코드와 동일하지만 상수 계수가 더 낮다.