⚠️ 문제
https://www.acmicpc.net/problem/5052
🔐 풀이
다른 비슷한 문제에서 접두어를 찾을 때 문자열 배열을 문자 길이 순으로 정렬하고 이를 이중 for문으로 확인했었는데, 이 문제를 똑같은 방법으로 풀면 시간 초과가 발생합니다.
이를 해결하기 위해서는 문자열 배열을 정렬했을 때의 특성을 파악해야 합니다.
아래와 같이 sort 함수에 인자 없이 문자열 배열을 정렬하면, 첫번째 문자를 기준으로 정렬하고 같으면 다음 문자를 기준으로, 또 같으면 다음 문자를 기준으로 정렬하는 방식이 됩니다.
arr = ["2346", "123", "123455", "234", "2345", "123456"]
arr.sort()
print(arr)
# ['123', '123455', '123456', '234', '2345', '2346']
따라서 한 번호가 다른 번호의 접두어라면, 배열을 정렬했을 때 그 두 번호는 인접해 있습니다.
이를 이용해 배열을 정렬한 후 인접하고 있는 두 번호만 비교하면 일관성 없는 번호를 찾을 수 있습니다.
🧑🏻💻 코드
import sys
t = int(sys.stdin.readline().rstrip())
for _ in range(t):
n = int(sys.stdin.readline().rstrip())
phone_number = []
for _ in range(n):
phone_number.append(sys.stdin.readline().rstrip())
phone_number.sort()
answer = True
for i in range(len(phone_number) - 1):
if phone_number[i] == phone_number[i+1][:len(phone_number[i])]:
answer = False
break
if answer:
print("YES")
else:
print("NO")