백준 5052 전화번호 목록
문제
https://www.acmicpc.net/problem/5052
접근방법
Trie 자료구조를 통해 구현하였다.
풀이코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static final int SIZE = 10;
static int N;
static Trie root;
private static class Trie {
boolean isLastNode;
Trie[] next;
public Trie() {
isLastNode = false;
next = new Trie[SIZE];
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(in.readLine());
for(int t=1; t<=T; ++t) {
// 1. 입력 및 초기화
N = Integer.parseInt(in.readLine());
root = new Trie();
// 2. Trie insert
String[] input = new String[N];
for(int i=0; i<N; i++) {
input[i] = in.readLine();
insert(input[i]);
}
// 3. 유효한 전화번호인지 확인
boolean ans = true;
for(int i=0; i<N; i++) {
if(!available(input[i])) {
ans = false;
break;
}
}
// 4. Answer
sb.append(ans ? "YES" : "NO").append("\n");
}
System.out.println(sb.toString().trim());
}
public static void insert(String str) {
Trie cur = root;
int len = str.length();
int index;
for(int i=0; i<len; i++) {
index = str.charAt(i) - '0';
if(cur.next[index] == null) { // 새로운 번호라면 추가
cur.next[index] = new Trie();
}
cur = cur.next[index]; // 다음 노드로 이동
}
cur.isLastNode = true; // 리프노드 지정
}
public static boolean available(String str) {
Trie cur = root;
int len = str.length();
int index;
for(int i=0; i<len; i++) {
index = str.charAt(i) - '0';
if(cur.isLastNode) { // 문자열 길이 전에 리프노드를 만난다면 유효하지 않는다.
return false;
}
cur = cur.next[index]; // 다음 노드로 이동
}
return true;
}
}