BOJ - 5052번 전화번호 목록(C++)

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

문제 난이도

Gold 4

문제 접근

이 문제는 트라이 알고리즘을 이용하거나, 정렬 후에 Map(해시 함수)를 이용해서 풀면된다.

나는 이 문제를 트라이로 풀었다. 트라이 알고리즘을 익히고 가장 기본으로 응용 될 수 있는 문제다.

Trie란?

트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조.
혹은 문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합을 표현하는 트리 형태의 자료구조이다.

트라이에서 데이터를 찾는 것은 불완전한 해시 테이블에 비해 최악의 경우 O (m) 시간 (여기서 m은 검색 문자열의 길이)에서 더 빠르다.

이해가 어렵다면 트리를 다시 공부하고 트라이를 보면 쉽게 이해가 간다.
트라이는 트리 형태이기 때문에, root 노드를 두고 각 문자를 root 자식 노드로 들어간다. 대신 단어의 끝일 때는 bool을 넣어 check를 해줘야하고, 기본적으로 구조체를 이용해서 구현한다.
보통 구조체에 insert(), find() 등 함수를 넣어 노드를 집어넣고 자리를 찾는다.

자세한 내용은 내가 문제풀며 참고한 링크를 넣어둔다.

Trie와 문제 5052 풀이도 잘 나타나 있다. 주석이 있어 이해하기 쉽다
Trie 기본 알고리즘을 확인하고 싶다면 이 링크를 참고하자

Trie 통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

struct Trie {
	Trie *next[10];
	bool finish;
	bool nextChild;

	Trie() { //생성자
		fill(next, next + 10, nullptr);
		finish = nextChild = false;
	}

	~Trie() { //소멸자
		for (int i = 0; i < 10; i++) {
			if (next[i])
				delete next[i];
		}
	}

	bool insert(const char *key) {
		if (*key == '\0') {
			finish = true;
			if (nextChild) return false;
			else return true;
		}
		int nextKey = *key - '0';
		if (!next[nextKey]) {
			next[nextKey] = new Trie;
		}
		nextChild = true;

		bool get = next[nextKey]->insert(key + 1);

		return !finish && get;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n;

		cin >> n;
		Trie *root = new Trie();

		bool isValid = true;
		for (int i = 0; i < n; i++) {
			char phone[11];
			cin >> phone;
			if (!root->insert(phone)) {
				isValid = false;
			}
		}
		string ans = isValid == true ? "YES\n" : "NO\n";
		cout << ans;
		delete root;
	}
	return 0;
}