[백준 5052번] 전화번호 목록 (java)

BOJ

lotus lee 2021. 2. 27. 22:06

5052번: 전화번호 목록

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가

www.acmicpc.net

트라이(Trie)를 이용하여 문제를 해결하였다.

트라이(Trie) 자료구조에 대한 기본적인 이해가 선행되어야 한다.

트라이(Trie) - 1. 트라이 개념 및 노드 특징

트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 트

lotuslee.tistory.com

전화번호에 일관성이 없는 경우는 트라이에서 문자열의 문자를 탐색하는 도중에, 마지막 문자가 아님에도 불구하고 isLastChar가 true인 노드가 존재하는 경우라고 볼 수 있다.

그래서 Trie 클래스 내에 checkConsist() 라는 메서드를 만들었다.

이 메서드는 특정 문자열을 탐색하는 도중에 isLastChar가 true 인 노드가 있으면 false를 반환한다.

문자열 중간에 있는 노드의 isLastChar가 true 라는 것은 전화번호가 일관성 없는 경우를 의미하기 때문이다.

checkConsist()가 false를 반환하면 NO를 출력하고, true를 반환하면 YES를 출력한다.