[백준(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;
}
}