[BOJ] 백준 5052번 전화번호 목록 (Java)

#5052 전화번호 목록

난이도 : 골드 4

유형 : 트라이 / 문자열 

5052번: 전화번호 목록

▸ 문제

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

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

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

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

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

▸ 입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

▸ 출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

 

문제 풀이  

정수나 실수는 그 크기가 항상 정해져 있기 때문에 비교에 상수 시간O(1)이 걸리는 반면, 문자열은 비교하는 데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 해당 문제는 최대 10자리를 가지는 10000개의 전화번호들의 일관성에 대한 여부를 알아내야 한다. 길이가 그렇게 길지 않으므로 일반적으로 하나씩 대조해가며 풀이를 해도 된다.

 

그러나 트라이(Trie) 자료구조에 대해 공부하고 있으므로 이를 사용해서 풀이를 할 것이다.

 

구상 및 설계

트라이(Trie) 자료구조를 구현하여 모든 전화번호 목록을 트라이에 저장해준다음 접두사가 일치하는지에 대한 여부를 조사해줄 것이다. 트라이 구조는 메모리를 엄청나게 낭비하지만 다음 노드를 찾는 과정에서 어떤 탐색도 필요하지 않다는 장점을 가지고 있다.

 

트라이(Trie)의 내부 구조는 2개의 상태로 이뤄져있다.

1. 자손 노드(childNode)를 가리키는 자료구조
2. 이 노드가 종료 노드인지를 나타내는 boolean값

class TrieNode{
	Map<Character, TrieNode> childNode = new HashMap<>();
	boolean terminal;
}

 

문자열(str)을 입력받으면 루트 노드를 시작으로 자식 노드로 내려가면서 각 문자열에 해당하는 문자들을 순차적으로 저장해준다. 트라이의 중요한 속성은 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사를 얻을 수 있다는 것이다.

public void insert(String word) {
	TrieNode trieNode = this;
	for(int i=0; i<word.length(); i++) {
		char c = word.charAt(i);

		// tmp childNode에 c없으면 추가 
		trieNode.childNode.putIfAbsent(c, new TrieNode());
		trieNode = trieNode.childNode.get(c);

		// 마지막 문자 terminal 
		if(i== word.length()-1) {
			trieNode.terminal = true;
			return;
		}
	}
}

 

 

다음 노드는 전화번호 {911, 91125, 97625}를 트라이 자료구조로 저장한 예시이다. 파란색으로 칠해진 노드는 종료 노드임을 나타낸다.

 

트라이 예시

 

이렇게 저장해준 트라이 자료구조를 통해 각 전화번호를 입력하여 해당 전화번호가 다른 전화번호의 접두사로 포함되는지에 대한 여부를 조사해주면 된다. 만약 현재 입력된 전화번호의 끝 부분이 다른 전화번호에 포함되는 부분이면 해당 전화번호 목록은 일관성이 있지않으므로 false를 반환한다. 

• 예를 들어 contains("911")을 한다고하면 911의 terminal노드가 "91125"의 중간부분에 해당하는 지점이므로 false를 반환해준다.

public boolean contains(String word) { 
	TrieNode trieNode = this;
	for(int i=0; i<word.length(); i++) {
		char c= word.charAt(i);
		TrieNode node = trieNode.childNode.get(c);

		if(node == null) {
			return false;
		}
		trieNode = node;
	}

	// 해당 단어로 종료하는 문자가 있는 경우 false 
	if(trieNode.terminal) {
		// 자기 자신 제외 (childNode가 없으면 해당 종료노드는 자기 자신임 ex) 911> 911) 
		if(trieNode.childNode.isEmpty()) {
			return false;
		}
	}
	return true;
}

풀이 코드 (Trie)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
	
	static class TrieNode{
		Map<Character, TrieNode> childNode = new HashMap<>();
		boolean terminal;
		
		TrieNode(){
			/** no-op **/
		}
		public void insert(String word) {
			TrieNode trieNode = this;
			for(int i=0; i<word.length(); i++) {
				char c = word.charAt(i);
				
				// tmp childNode에 c없으면 추가 
				trieNode.childNode.putIfAbsent(c, new TrieNode());
				trieNode = trieNode.childNode.get(c);
				
				// 마지막 문자 terminal 
				if(i== word.length()-1) {
					trieNode.terminal = true;
					return;
				}
			}
		}
		
		public boolean contains(String word) { 
			TrieNode trieNode = this;
			for(int i=0; i<word.length(); i++) {
				char c= word.charAt(i);
				TrieNode node = trieNode.childNode.get(c);
				
				if(node == null) {
					return false;
				}
				trieNode = node;
			}
			
			// 해당 단어로 종료하는 문자가 있는 경우 false 
			if(trieNode.terminal) {
				if(trieNode.childNode.isEmpty()) {
					return false;
				}
			}
			return true;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());

		for (int i = 0; i < t; i++) {
			int n= Integer.parseInt(br.readLine());
			TrieNode trie = new TrieNode();
			boolean isConsistent = true;
			
			List<String> keyList = new ArrayList<>();
			for (int j = 0; j < n; j++) {
				String str = br.readLine();
				trie.insert(str);
				keyList.add(str);
			}
			
			for(String key : keyList) {
				if(trie.contains(key)) {
					isConsistent = false;
					break;
				}
			}
			System.out.println(isConsistent?"YES":"NO");
		}
	}
}

 

풀이 코드 (일반 문자열 비교)

해당 문제에서 주어진 문자열의 범위가 그리 크지 않기 때문에 이와 같이 직접 비교해줘도 된다. 완전탐색으로 모든 문자열을 모두 비교해주는 방식으로 한 문자열이 다른 문자열의 시작부분에 포함되면 "NO"를 출력해준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for (int i = 0; i < t; i++) {
			int n= Integer.parseInt(br.readLine());
			String[] s = new String[n];
			int check = 0;
			for (int j = 0; j < n; j++) {
				s[j] = br.readLine();
			}
			
			Arrays.sort(s, new Comparator<String>() {
				@Override
				public int compare(String o1, String o2) {
					return o1.compareTo(o2);
				}
			});
			
		   for(int j=1;j<n;j++) {
                if(s[j].startsWith(s[j-1])) {
                    check=1;
                    break;
                }
            }
            System.out.println(check==0?"YES":"NO");
		}
	}
}