최's 먹공로그
BOJ5052 전화번호 목록 본문
<문제 요약>
https://www.acmicpc.net/problem/5052
1. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
ex) 911, 97625999, 91125426 인 경우
2. 전화번호의 길이는 최대 10자리, 같은 경우는 없다.
3. 각 테스트 케이스에 대해서 일관성이 있으면 YES, 없으면 NO
<풀이흐름, Source Code>
1. Trie 자료구조를 사용한다.
911, 91125426, 97625999을 Trie에 넣고 list에 add 해준다.
각 배열의 10번째 칸에 체크가 된 경우 전화번호의 끝임을 알려준다.
2. add가 끝났으면 list에 있는 전화번호를 돌면서 10번째 칸이 체크된 전화번호인지 확인 해준다.
전화번호의 자리를 한개 씩 검사하다가 중간에 10번째 칸이 체크된 전화번호라면 접두어가 같은 다른 전화번호가 존재
3. 접두어가 같은 다른 전화번호가 존재하면 NO를 StringBuilder에 더해주고 아닌경우 YES를 더해준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class BOJ5052_전화번호목록 {
private static class Node{
Node[] data;
Node(){
data = new Node[11];
}
Node getChild(int idx) {
return data[idx];
}
void setChild(int idx) {
data[idx] = new Node();
}
}
private static class Trie{
Node root;
Trie(){
root = new Node();
}
void init() {
root = new Node();
}
char[] add(char[] c) {
Node n = root;
for(int i = 0; i < c.length; i++) {
int idx = c[i] - '0';
if(n.data[idx] == null) {
n.setChild(idx);
}
n = n.getChild(idx);
}
n.setChild(10);
return c;
}
boolean check(char[] c) {
Node n = root;
for(int i = 0; i < c.length; i++) {
int idx = c[i] - '0';
if(n.data[10] != null) {
return false;
}
n = n.getChild(idx);
}
return true;
}
}
static ArrayList<char[]> list = new ArrayList<char[]>();
static Trie trie = new Trie();
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc = 1; tc <= T; tc++) {
trie.init();
list.clear();
int size = Integer.parseInt(br.readLine());
for(int i = 0; i < size; i++) {
list.add(trie.add(br.readLine().toCharArray()));
}
sb.append((isPossible(size) ? "YES" : "NO") + "\n");
}
System.out.print(sb.toString());
}
private static boolean isPossible(int size) {
for(int i = 0; i < size; i++) {
if(!trie.check(list.get(i))) {
return false;
}
}
return true;
}
}
<문제 Issue>
X
<중요 정리>
1. Trie 자료구조 학습!
- Trie 자료구조는 Tree를 기반으로 만든다.
- Trie 자료구조의 시간 복잡도는 O(문자열 길이)라는 매우 빠른 시간 복잡도를 가진다.
- 하지만, 모든 Node마다 배열을 만들어 줘야 해서 Tree Depth가 깊어지면 메모리가 터질 수 있다.
- 보통 Trie를 사용하는 문제의 경우 Tree Depth의 최대값을 지정해둔다. 위 문제의 경우 전화번호의 최대 길이인 10
- Trie 자료구조를 구현할 때 한 개의 Depth라도 줄이기 위해서 Trie생성자 혹은 init()이 호출될 때 new Node()를 하도록 했다.
'Pro감옥' 카테고리의 다른 글
BOJ25240 가희와 파일 탐색기2 (0) | 2022.10.01 |
---|---|
BOJ1202 보석도둑 (0) | 2022.09.29 |
[자료구조] 힙(heap) (10) | 2021.04.29 |