백준 5052 전화번호 목록 c++ (트라이)

문제 출처 : https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

문제

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

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

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

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

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

입력

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

출력

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

알고리즘 분류

• 자료 구조
• 문자열
• 정렬
• 트리
• 트라이

풀이

문자열을 빠르게 탐색하게 해주는 트라이 자료구조를 사용해야 하는 문제이다.

처음엔 그냥 vector에 전화번호를 저장하고, 접두어가 있는지 확인했는데 시간 초과가 떠서 방법을 찾아보니,

트라이(TRIE)라는 자료구조에 대해 알게 되었다.

트라이 자료구조만 알면 쉽게 풀 수 있는 문제이고, 트라이 자료구조는 추후 업로드 예정이다.

 

코드

#include <iostream>
#include <string>

using namespace std;

char input[10000][11];

struct TRIE {
	
	bool Finish;
	TRIE *Node[10];
	TRIE() {
		Finish = false;
		for (int i = 0; i < 10; i++) {
			Node[i] = NULL;
		}
	}

	void insert(char *str) {
		if (*str == '\0') {
			Finish = true;
			return;
		}
		int Cur = *str - '0';
		if (Node[Cur] == NULL) Node[Cur] = new TRIE();
		Node[Cur]->insert(str + 1);
	}

	bool find(char *str) {
		//끝까지 도달하면 return false
		if (*str == '\0') {
			return false;
		}
		//중간에 finish가 있으면 일관성 x (어떤 전화번호가 다른 전화번호의 접두어가 되면)
		if (Finish == true)
			return true;

		int Cur = *str - '0';
		if (Node[Cur] == NULL) return false;
		return Node[Cur]->find(str + 1);
	}


};


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	

	int t, n;
	cin >> t;
	while (t--) {
		cin >> n;
		TRIE *Root = new TRIE();
		for (int i = 0; i < n; i++) {
			cin >> input[i];
			Root->insert(input[i]);
		}
		int i;
		for(i=0; i<n;i++){
			if (Root->find(input[i])) {
				cout << "NO\n";
				break;
			}
		}
		if (i == n)
			cout << "YES\n";
	}

	return 0;
}

코드(Kotlin)

import java.util.*
class Trie(var finish : Boolean, var node : MutableMap<Char,Trie>){

    fun insert(word : String){
        var children : Trie = this
        for(ch in word){
            //노드에 ch엣지가 연결되어 있으면 이동
            if(children.node.containsKey(ch)){
                children = children.node[ch]!!
            }
            else{ //엣지가 연결되어 있지 않으면 새로 생성 후 연결
                children.node[ch] = Trie(false, mutableMapOf<Char,Trie>())
                children = children.node[ch]!!
            }
        }
        //단어의 끝에 finish
        children.finish=true
    }
    fun check(word :String):Boolean{
        var children =this
        for(ch in word){
            //엣지를 따라서 이동 중간에 finish가 있으면 일관성 x(어느 번호가 word의 접두어가 되는 경우)
            if(children.node.containsKey(ch)){

                if(children.finish){//중간에 끝난 문자가 있으면 no
                    return false
                }
                children = children.node[ch]!!
            }
        }
        //word 검사 시 문제가 없으면 yes
        return true
    }
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    var t = Integer.parseInt(br.readLine())
    while(t--!=0) {
        val n = Integer.parseInt(br.readLine())
        var answer = "YES"
        val root = Trie(false, mutableMapOf())
        val input = Array<String>(n){""}
        for(i in 0 until n){
            input[i] = br.readLine()
            root.insert(input[i])
        }
        for(i in 0 until n){
            if(!root.check(input[i])){
                answer="NO"
                break
            }
        }
        write("${answer}\n")
    }


    close()
}