[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;
    }
}