[BOJ] 5052 전화번호 목록

5052번: 전화번호 목록

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 

입력

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

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

---

Trie라는 새로운 자료구조를 알게 돼서 그 내용을 다루는 문제를 풀어보았다. Trie는 문자열 처리에 확실히 좋아 보였다. 그리고 아마 처음으로 이진트리가 아닌 트리 구조를 구현해서 사용해본 것 같다.

 

대신 문자열에 사용되는 문자가 한정되어 있지 않고 다양하게 들어오면 메모리가 박살 나지 않을까 싶다. 그런 경우에도 Trie를 사용하기 위해선 내가 사용한 방법처럼 정적 할당하면 안 된다.

 

문제 자체는 Trie만 알고 있다면 쉽게 풀리는 문제였다. Trie 말고 다른 방법으로도 해결할 수 있는 문제였던 것 같지만 Trie를 연습해보기 위해서 굳이 Trie를 사용했다. 

 

처음엔 Trie에 문자열을 삽입하면서 일관성 검사를 바로 했었는데 다음과 같은 반례가 존재한다.

1
2
9115
911
ans:NO

두 번째 문자열이 첫 번째 문자열의 접미사이기 때문에 일관성이 없다고 판정되지만 접미사인 문자열이 더 늦게 입력되기 때문에 일관성 판정에 오류가 생긴다. 그래서 뒤에 어떤 문자열이 들어올지 모르는 이상 일관성 판정이 불가능해진다.

 

그래서 우선 입력을 받으면서 Trie에 삽입한 이후에 Trie 구성이 끝나면 일관성 판정을 했다. 그런데 이렇게 일관성 판정을 하게 되는 경우엔, 같은 문자열을 검사하면서 일관성이 없다고 판정이 되지 않을까 싶었는데 그런 문제는 발생하지 않았다. 그 이유는 문자열이 "911" 문자열이 들어오면 마지막 1에 end flag가 set 되는 것이 아니라 널 문자에 set 되게 된다. 따라서 문제가 발생하지 않는다.

 

그리고 문자열이 길 수 록 접미사가 있을 확률이 높다고 생각했다. 문자열의 길이가 긴 것부터 일관성 판정을 하면 판정이 빠르게 돼서 실행 시간이 줄어들 것 같았다. 그래서 내림차순으로 정렬한 이후에 일관성 판정을 해봤다. 그런데 오히려 더 시간이 많이 걸렸다. 아마도 정렬하면서 발생하는 오버헤드가 훨씬 컸던 것 같다.

 

후기)

또 새로운 자료구조를 익혔다. 문자열 처리 문제를 많이 풀어보지 않아서 전혀 모르고 있던 자료구조였다.