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를 출력한다.
소스코드 :
'BOJ' 카테고리의 다른 글
| [백준 2343번] 기타 레슨 (java) (0) | 2021.03.01 |
|---|---|
| [백준 6236번] 용돈 관리 (java) (0) | 2021.03.01 |
| [백준 2056번] 작업 (java) (0) | 2021.02.26 |
| [백준 2670번] 연속부분최대곱 (java) (0) | 2021.02.25 |
| [백준 2240번] 자두나무 (java) (0) | 2021.02.25 |