https://www.acmicpc.net/problem/5052
문제에서 전화번호 목록이 주어지면 목록에 있는 전화번호들은 번호가 겹쳐지면 안되는 문제,
각 번호들이 겹쳐지는지 아닌지 확인해야하는 문제 절대 짧은 문자를 기준으로 겹쳐지는 것을 찾는 것이 아니다!!
하나씩 전부 비교한다. 하나씩 전부 비교하게 된다면 O(N^2)의 시간이 필요하다. => 시간초과
전화번호를 오름차순으로 정렬한다.
파이썬에서 문자열을 오름차순으로 정렬하게 된다면 문자 하나하나씩 아스키코드로 비교하고 그래도 같다면 문자 길이로 정렬한다. 예를 들면 [911,9112345] 리스트가 있다면 911까지 비교하고 그 뒤로 길이순서대로 정렬한다. 만약 [9112346,9112345] 리스트라면 [9112345,9112346]으로 정렬 될 것이다.
이렇게 된다면 앞부분이 겹쳐지는 부분을 우선으로 정렬하고 그 다음 정렬조건으로 길이로 비교하게된다.
이렇게 정렬하게 된다면 O(N)으로 겹쳐지는 전화번호가 있는지 없는지 파악 할 수 있다.
import sys
from collections import deque
def checker_string(string_arr:deque):
for i in range(1,len(string_arr)):
tmp1 = string_arr[i]
tmp2 = string_arr[i-1]
if tmp1.startswith(tmp2):
return False
return True
for tc in range(int(sys.stdin.readline())):
n = int(sys.stdin.readline())
string_arr = deque()
for i in range(n):
string_arr.append(sys.stdin.readline().rstrip())
string_arr = deque(sorted(string_arr))
if checker_string(string_arr):
print("YES")
else:
print("NO")