8024 : 전화번호 목록
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
전화번호부가 주어집니다. 이 전화번호부가 일관성(Consistent)을 가지려면, 어떤 전화번호도 다른 전화번호의 접두사(Prefix)가 되어서는 안 됩니다.
예를 들어 긴급 전화번호
전화번호부가 일관성을 가지는지 판별하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le t \le 50$ (테스트 케이스 수)
• $1 \le n \le 10,000$ (전화번호 수)
• 각 전화번호의 길이는 $1$ 이상 $10$ 이하의 숫자로 이루어집니다.
예를 들어 긴급 전화번호
911이 있고 누군가의 번호가 9116316이라면, 전화 교환원이 9116316을 다이얼할 때 911로 먼저 연결될 수 있으므로 이 전화번호부는 일관성이 없습니다.전화번호부가 일관성을 가지는지 판별하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le t \le 50$ (테스트 케이스 수)
• $1 \le n \le 10,000$ (전화번호 수)
• 각 전화번호의 길이는 $1$ 이상 $10$ 이하의 숫자로 이루어집니다.
입력 설명
첫째 줄에 테스트 케이스의 개수 $t$가 주어집니다.
각 테스트 케이스의 첫째 줄에는 전화번호의 개수 $n$이 주어집니다.
다음 $n$개의 줄에 걸쳐 전화번호가 한 줄에 하나씩 주어집니다.
각 테스트 케이스의 첫째 줄에는 전화번호의 개수 $n$이 주어집니다.
다음 $n$개의 줄에 걸쳐 전화번호가 한 줄에 하나씩 주어집니다.
출력 설명
각 테스트 케이스에 대해, 전화번호부가 일관성이 있으면
YES, 일관성이 없으면 NO를 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
출력 예시
COPY
복사되었습니다!
복사되었습니다!
NO
YES도움
문자열 트라이(Trie) 자료구조를 구축하면서 새로운 번호가 기존 번호의 접두사이거나 기존 번호를 접두사로 포함하는지 검사하거나, 전화번호 목록을 사전순으로 정렬한 뒤 인접한 두 문자열 사이의 접두사 관계만 검사하면 $O(N \log N \times L)$ 시간에 빠르게 판별할 수 있습니다.