[백준] 5052 : 전화번호 목록 (파이썬)

해시, 문자열, 트라이 문제

https://www.acmicpc.net/problem/5052

---

💡 풀이코드 (성공)

import sys 
t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    arr = []

    for _ in range(n):
        num = str(sys.stdin.readline().strip()) # strip 추가하여 해결 
        arr.append(num)
    arr.sort()

    def sol(n, arr):
        phone_num = set()

        for num in arr:
            for i in range(len(num) - 1):
                if num[:i+1] in phone_num:
                    print("NO")
                    return 
            phone_num.add(num)
        print("YES")
    sol(n, arr)

 

해시 알고리즘

이 문제를 보고, 초기에는 해시 알고리즘을 활용해야 겠다는 생각을 하지 못했다.

문제에 해시 알고리즘을 활용하자. 파이썬에서 해시를 기반으로 작동하는 자료구조인 딕셔너리(dict)나 집합(set)을 활용하자.

• 딕셔너리 : 키-값 쌍으로 데이터를 저장하는 구조 
• 집합 : 고유한 원소들의 집합으로, 각 원소들끼리는 중복을 허용하지 않는다.

---

주요 로직

1. 입력으로 받은 전화번호 목록을 정렬한다.

• 한 번호가 다른 번호의 접두어와 같은지 확인하기 위함이다.
•  만약 91125426이 911보다 먼저 나올 경우, 위의 케이스에 부합하지만 조건문에 걸리지 않는다. -> "YES" 출력
• 따라서 911이 91125426보다 항상 먼저 나오도록 하여, 조건문에 걸리도록 해야 한다. -> "NO" 출력

2. 중복되지 않은 전화번호 목록을 저장한 phone_num이란 set을 만든다.

phone_num = set()​

 

3. 정렬한 전화번호 목록을 순회하기 위해 for문을 돈다.

• 이때, 각 전화번호의 길이만큼 이중 for문을 돈다. (전화번호의 길이 <= 10자리)
• 만약 각 전화번호의 처음 ~ i + 1번째 문자 바로 전까지의 부분 문자열이 set에 있다면
  즉, 현재 전화번호의 접두어가 중복되지 않은 전화번호 목록(set)에 있는 전화번호와 겹친다면
  "NO"를 출력하고 리턴한다.

for num in arr:
    for i in range(len(num) - 1):
        if num[:i+1] in phone_num:
            print("NO")
            return​

• 그렇지 않다면, 현재 전화번호를 중복되지 않은 전화번호 목록(set)에 추가해준다.
• 함수가 리턴되지 않고, 끝까지 도달했다면 "YES"를 출력한다.

---

시간 복잡도 

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

 

계산

t = 테스트 케이스 개수

n = 각 테스트 케이스의 첫째 줄에는 전화번호의 수

m = 전화번호의 길이

 

• 정렬 : O(t * n * m * log(n)
• 접두어 확인 : O(t * (n * m ))

최종

O(t * n * m * log(n)이다.

따라서, 최악의 경우 50 * 10000 * 10 * log(10000) = 66,438,561 (6천만) 시간이 걸린다.

---

https://ansohxxn.github.io/boj/5052/

[백준 5052][💛4] 전화번호 목록 (해시, 트라이)

https://ansohxxn.github.io/algorithm/trie/#google_vignette

(C++) 문자열 집합 : 트라이 자료구조