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

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

문제 : BOJ_5052번 전화번호 목록

문제 설명

Trie(트라이)

트라이 문제 중 기본적인 문제입니다.
전화번호들을 입력받는데, 해당 번호의 첫 번호부터 끝 번호가 다른 전화번호의 첫 번호부터 해당되있으면
일관성이 없는 것이라고 판단해야하고, 서로 겹치지않으면 일관성이 있는 것이라고 판단해야합니다.


Solution

java로 트라이구조를 구현해서 풀어보았습니다.
String을 입력받은 뒤, String을 한 글자씩 for문으로 돌려가며,
해당 자식 번호가 없으면 Trie 인스턴스를 만들어주고, 자식의 유무와 단어의 끝 유무를 파악했습니다.


Description

테스트케이스마다 생성되는 트라이 그래프의 일관성은 정적 변수로 체크했습니다.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Java_5052_전화번호목록 {

	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());
			Trie trie = new Trie();
			for(int j=0;j<n;j++) {
				String word = br.readLine();
				trie.insert(word);
			}
			if(Trie.isConsistency) System.out.println("YES");
			else System.out.println("NO");
			Trie.isConsistency=true;
		}
	}

}

class Trie {
	static boolean isConsistency=true;
	// 정적 변수
	boolean isWord = false;
	boolean existChild = false;
	// 디폴트 속성
	Trie[] childTrie = new Trie[10];
	void insert(String word) {
		int len = word.length();
		Trie nowTrie = this;
		for(int i=0;i<len;i++) {
			int nextNum = word.charAt(i)-'0';
			if(nowTrie.childTrie[nextNum]==null) nowTrie.childTrie[nextNum] = new Trie();
			nowTrie = nowTrie.childTrie[nextNum];
			// 자식 그래프로 이동
			if(i==len-1) nowTrie.isWord=true;
			else nowTrie.existChild=true;
			if(nowTrie.isWord && nowTrie.existChild) isConsistency = false;
		}
	}
}

cpp로 짠 코드도 첨부합니다.

#include <iostream>
#include <cstring>
using namespace std;
bool isConsistent = true;
struct Trie {
	bool isWord;
	bool existChild;
	Trie* childTrie[10];
	Trie() {
		isWord = false;
		existChild = false;
		for (int i = 0; i < 10; i++) childTrie[i] = nullptr;
	}
	~Trie() {
		for (int i = 0; i < 10; i++) {
			if (childTrie[i]) delete childTrie[i];
		}
	}

	void insert(char* word) {
		if (*word == '\0') isWord = true;
		else {
			int next = *word - '0';
			if (!childTrie[next]) childTrie[next] = new Trie;
			existChild = true;
			childTrie[next]->insert(word + 1);
		}
		if (isWord && existChild) isConsistent = false;
	}
};
int main(void) {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		isConsistent = true;
		Trie* trie = new Trie;
		int N;
		cin >> N;
		for (int j = 0; j < N; j++) {
			char word[11];
			cin >> word;
			trie->insert(word);
		}
		if (isConsistent) cout << "YES\n";
		else cout << "NO\n";
		delete trie;
	}
}