BOJ5052 전화번호 목록

<문제 요약>

https://www.acmicpc.net/problem/5052

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()를 하도록 했다.