[BOJ] #5052 전화번호 목록

시간 제한	메모리 제한	정답 비율
1 초	256 MB	29.753 %

5052번: 전화번호 목록

 

문제

 

해결

key point, TRIE(트라이) 자료구조를 사용한다.

1. 입력받은 n개의 전화번호로 전화번호 목록을 만든다. → insert()
2. n개의 전화번호로 모두 구성한 전화번호 목록에서 "한 번호가 다른 번호의 접두어인 경우"를 탐색한다. → find()
   1. 한 번호가 다른 번호의 접두어인 경우라면 flg 변수의 값을  true로 변경
   2. 아니라면, flg는 그대로 false
3. flg값이 true라면 일관성이 없는 목록이므로 NO를 출력하고
4. ture라면 YES를 출력한다.

 

트라이

전화번호로 트라이를 구성할 때는 어떠한 단어도 들어가지 않는 하나의 루트(최상위 노드)에 n개의 전화번호를 모두 저장했다. 

루트는 0~9까지의 child배열을 갖고 있으며 각각의 배열은 TRIE 포인터이다.

insert 함수 내에서는, 입력된 문자열( = 인자로 전달된 문자열 = key)을 가지고 차례대로 자식 노드로 이동해가면서, 자식 노드가 비어있을경우 만들어주고, 입력된 문자열의 끝을 만났다면 is_terminal을 true로 바꿔 해당 노드가 문자열의 마지막이라는 것을 알 수 있게 한다.

find 함수 내에서는, 전화번호 목록에서 key의 접두어가 있는지 없는지 찾는 연산을 한다. key의 전화번호를 전화번호 목록을 따라 가면서 탐색을 하는데, key가 마지막 문자가 아니면서 전화번호 목록에서 먼저 끝나는 노드가 있다면 접두어를 찾은 것이므로 true를 리턴하고, 접두어를 찾지 못했다면 마지막은 자기자신이므로 '\0'문자가 되어 false가 리턴되게 된다.

 

코드

메모리	시간
8056 KB	136 ms