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

5052번: 전화번호 목록

 

트라이(Trie)를 이용하여 문제를 해결하였다.

트라이(Trie) 자료구조에 대한 기본적인 이해가 선행되어야 한다.

트라이(Trie) - 1. 트라이 개념 및 노드 특징

전화번호에 일관성이 없는 경우는 트라이에서 문자열의 문자를 탐색하는 도중에, 마지막 문자가 아님에도 불구하고 isLastChar가 true인 노드가 존재하는 경우라고 볼 수 있다.

 

그래서 Trie 클래스 내에 checkConsist() 라는 메서드를 만들었다.

이 메서드는 특정 문자열을 탐색하는 도중에 isLastChar가 true 인 노드가 있으면 false를 반환한다.

문자열 중간에 있는 노드의 isLastChar가 true 라는 것은 전화번호가 일관성 없는 경우를 의미하기 때문이다.

checkConsist()가 false를 반환하면 NO를 출력하고, true를 반환하면 YES를 출력한다.

 

소스코드 :

	import java.io.*;
	import java.util.*;
	public class n05052 {
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	int t = Integer.parseInt(br.readLine());
	for (int i = 0; i < t; i++) {
	int n = Integer.parseInt(br.readLine());
	Trie trie = new Trie();
	List<String> list = new ArrayList<>();
	for (int j = 0; j < n; j++) {
	String str = br.readLine();
	list.add(str);
	trie.insert(str);
	}
	boolean flag = true;
	for (int j = 0; j < list.size(); j++) {
	if (!trie.checkConsist(list.get(j))) {
	flag = false;
	break;
	}
	}
	if (flag)
	bw.write("YES\n");
	else
	bw.write("NO\n");
	}
	bw.flush();
	}
	static class Trie {
	TrieNode rootNode;
	Trie() {
	rootNode = new TrieNode();
	}
	public void insert(String word) {
	TrieNode thisNode = this.rootNode;
	for (int i = 0; i < word.length(); i++) {
	thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), key -> new TrieNode());
	}
	thisNode.setIsLastChar(true);
	}
	public boolean contain(String word) {
	TrieNode thisNode = this.rootNode;
	for (int i = 0; i < word.length(); i++) {
	thisNode = thisNode.getChildNodes().get(word.charAt(i));
	if (thisNode == null)
	return false;
	}
	return thisNode.isLastChar();
	}
	public boolean delete(String word) {
	return delete(rootNode, word, 0);
	}
	public boolean delete(TrieNode thisNode, String word, int index) {
	char ch = word.charAt(index++);
	TrieNode childNode = thisNode.getChildNodes().get(ch);
	if (index == word.length()) {
	if (!childNode.isLastChar())
	return false;
	childNode.setIsLastChar(false);
	if (childNode.getChildNodes().isEmpty())
	thisNode.getChildNodes().remove(ch);
	return true;
	}
	if (delete(childNode, word, index)) {
	if (!childNode.isLastChar() && childNode.getChildNodes().isEmpty())
	childNode.getChildNodes().remove(ch);
	return true;
	}
	return false;
	}
	public boolean checkConsist(String word) {
	TrieNode thisNode = rootNode;
	for (int i = 0; i < word.length(); i++) {
	thisNode = thisNode.getChildNodes().get(word.charAt(i));
	if (i < word.length() - 1 && thisNode.isLastChar())
	return false;
	}
	return true;
	}
	}
	static class TrieNode {
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	private boolean isLastChar;
	public Map<Character, TrieNode> getChildNodes() {
	return childNodes;
	}
	public void setIsLastChar(boolean isLastChar) {
	this.isLastChar = isLastChar;
	}
	public boolean isLastChar() {
	return isLastChar;
	}
	}
	}

view raw 5052.java hosted with ❤ by GitHub