백준 5052 (전화번호 목록) -Trie

문제

---

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 

 

 

 

풀이

---

문자열중 하나의 문자열이 다른 문자열의 접두사가 되는지를 확인하는 문제다 Trie 알고리즘을 이용해서 풀었다.

 

Trie 알고리즘은 문자를 가지고 트리형태로 구성해서 푸는 문제다.

 

conpulake.tistory.com/54?category=852837

백준 9202 (Boggle)

여기서 Trie 알고리즘을 한번 다룬적이 있다.

 

이 문제에서는 어떤 문자열에서는 끝지점인데 자식이 존재하면 접두사가 된다는 것으로 판단하고 풀었다.

 

911

97625999

91125426

 

위의 예를 들면 9 1 1의 1지점에서 911 문자열은 끝이기때문에 문자열의 끝이라는 값을 boolean으로 넣어준다.

하지만 91125426의 경우는 1 이후에 2를 넣어주어야하기 때문에 1노드에 자식이 존재한다.

 

이경우를 접두사가 된다고 판단하고 NO를 출력하게 했다.

 

static class Trie{
		
	public Trie[] number;
	public boolean isEnd;
	public char num;
	
	public Trie(char num) {
		this.num = num;
		number = new Trie[10];
		isEnd = false;
	}
}

위 코드가 Trie 알고리즘을 사용할 때 사용한 클래스다.

여기선 숫자만 다루기 때문에 저장을 용이하게 하기 위해 배열로 했지만 List로 해도된다.

 

for(int i = 0 ; i < m ; i++) {
	string[i] = bufferedReader.readLine();
	Trie start = root;
	for(int j = 0 ; j < string[i].length() ; j++) {
		if(start.number[string[i].charAt(j) - '0'] == null) {
			start.number[string[i].charAt(j) - '0'] = new Trie(string[i].charAt(j));
		}
		start = start.number[string[i].charAt(j) - '0'];
		if(j == string[i].length() - 1) {
			start.isEnd = true;
		}
	}				
}

문자열을 문자하나하나 트리에 넣어주는 과정이다. 

해당 문자열이 끝이라면 isEnd 값을 true로 바꿔준다.

 

static boolean isTrue(Trie root) {
		
	Trie start = root;
	
	boolean result = true;
	boolean haveChild = false;
	for(int i = 0 ; i < 10 ; i++) {
		if(start.number[i] != null) {
			result = isTrue(start.number[i]);
			haveChild = true;
			if(!result)
				break;
		}
	}
	
	if(haveChild && start.isEnd)
		return false;
	
	return result;
}

DFS방식을 이용해서 풀었다. 자식이 존재하지만 isEnd 인경우는 false값을 넣어줬다.

result 가 false 면 뒤에 값들은 안봐도 되므로, 바로 return 해주었다.

 

 

<전체코드>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static class Trie{
		
		public Trie[] number;
		public boolean isEnd;
		public char num;
		
		public Trie(char num) {
			this.num = num;
			number = new Trie[10];
			isEnd = false;
		}
		
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bufferedReader.readLine());
		for(int testIndex = 0 ; testIndex < n ; testIndex++) {
			int m = Integer.parseInt(bufferedReader.readLine());
			
			String[] string = new String[m];
			Trie root = new Trie('\0');
			for(int i = 0 ; i < m ; i++) {
				string[i] = bufferedReader.readLine();
				Trie start = root;
				for(int j = 0 ; j < string[i].length() ; j++) {
					if(start.number[string[i].charAt(j) - '0'] == null) {
						start.number[string[i].charAt(j) - '0'] = new Trie(string[i].charAt(j));
					}

					start = start.number[string[i].charAt(j) - '0'];
					if(j == string[i].length() - 1) {
						start.isEnd = true;
					}
				}				
			}
			
			if(isTrue(root))
				sb.append("YES\n");
			else
				sb.append("NO\n");
			
		}
		
		System.out.println(sb);
	}
	
	static boolean isTrue(Trie root) {
		
		Trie start = root;
		
		boolean result = true;
		boolean haveChild = false;
		for(int i = 0 ; i < 10 ; i++) {
			if(start.number[i] != null) {
				result = isTrue(start.number[i]);
				haveChild = true;
				if(!result)
					break;
			}
		}
		
		if(haveChild && start.isEnd)
			return false;
		
		return result;
	}
}