백준 5052번 전화번호 목록

< 백준 5052번 전화번호 목록 - 마포 코딩박 >

사용한 알고리즘: Trie


 해당 문제는 Trie 를 구현할 수 있는지 묻는 문제였습니다.
 문자열 구현에 어려움을 느껴 강산씨 블로그 (ries 네이버블로그) 을 많이 참고하였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~45)
 트라이를 구현하는 struct 를 만듭니다.
 struct 는 생성자, 소멸자, insert 함수, 일관성을 판단하는 함수 로 구성됩니다.

(2) (코드 49~61)
 N개의 입력되는 전화번호들을 과정(1)의 struct 로 저장하고, 이 전화번호들의 일관성을 판단해 줍니다.

	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	const int GO_MAX = 10; // 트라이 노드마다 포인터 개수
	// 강산씨 (ries 네이버블로그)의 글을 많이 참고하여 작성하였습니다.
	struct Trie{
	Trie* go[GO_MAX]; // 다음 노드를 가리키는 포인터 배열
	bool output; // 이 노드에서 끝나는 전화번호가 있는가?
	bool goexist; // 이 노드의 자식이 있는가?
	// 생성자
	Trie(){
	fill(go, go+GO_MAX, nullptr);
	output = goexist = false;
	}
	// 소멸자
	~Trie(){
	for(int i=0; i<GO_MAX; i++)
	if(go[i]) delete go[i];
	}
	// 문자열 key를 현재 노드부터 삽입
	void insert(const char* key){
	// 문자열이 끝남
	if(*key == '\0') output = true;
	// 아닐 경우
	else{
	int next = *key - '0';
	// 해당 노드가 없으면 새로 동적 할당해서 만듬
	if(!go[next]) go[next] = new Trie;
	goexist = true;
	// 자식 노드에서 이어서 삽입
	go[next]->insert(key+1);
	}
	}
	// 이 노드가 일관성이 있는가?
	bool consistent(){
	// 자식도 있으면서 여기서 끝나는 전화번호도 있다면 일관성 없음
	if(goexist && output) return false;
	// 자식들 중 하나라도 일관성이 없으면 이 노드도 일관성이 없음
	for(int i=0; i<GO_MAX; i++)
	if(go[i] && !go[i]->consistent()) return false;
	// 일관성이 있음
	return true;
	}
	};
	int main(){
	int T;
	scanf("%d", &T);
	for(int t=0; t<T; t++){
	int N;
	scanf("%d", &N);
	Trie *root = new Trie; // 루트 노드 만들기
	for(int i=0; i<N; i++){
	char tel[11];
	scanf("%s", tel);
	root->insert(tel);
	}
	puts(root->consistent() ? "YES" : "NO");
	// 소멸자를 호출하여 동적 할당 해제를 하지 않으면 힙 메모리가 부족할 수 있음
	delete root;
	}
	return 0;
	}

view raw BOJ 5052.cpp hosted with ❤ by GitHub