728x90
SMALL
해시, 문자열, 트라이 문제
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/
https://ansohxxn.github.io/algorithm/trie/#google_vignette
728x90
LIST