BOJ 5052 - 전화번호 목록

링크: https://www.acmicpc.net/problem/5052

문제

한 문자열이 다른 문자열의 접두어(prefix)이면 NO, 그런 경우가 없으면 YES를 출력하는 문제이다.

풀이 1 (정렬)

모든 문자열을 사전순으로 정렬하면, 접두어가 겹치는 문자열끼리 붙어있다.

어떤 문자열이 직전 문자열의 부분 문자열인지 확인하면 된다.

시간 복잡도는 정렬 + 부분 문자열 확인 시간만큼이므로, $O(nlogn + n|s_{max}|)$

코드 1 (정렬)

	#include <bits/stdc++.h>
	using namespace std;
	int main(){
	int T, n, i;
	cin >> T;
	while(T--){
	cin >> n;
	string s;
	vector<string> v(n);
	for(i=0; i < n; ++i) cin >> v[i];
	sort(v.begin(), v.end());
	bool answer = true;
	for(i=0; i < n - 1; ++i){
	if(v[i] == v[i + 1].substr(0, v[i].length())){
	answer = false;
	break;
	}
	}
	cout << (consist ? "YES":"NO") <<endl;
	}
	return 0;
	}

view raw boj-5052-sort.cpp hosted with ❤ by GitHub

풀이 2 (트라이; Trie)

분류에 트라이가 있기도 하고, 트라이를 한번도 구현해본 적 없어서 트라이로 풀어봤다.

문자열을 하나씩 확인하며 트라이를 만들어간다.

어떤 문자열이 끊긴 지점에 "이 곳이 하나의 단어였다"로 리프 표시를 해두고 넘어간다.

다음에 트라이를 만드는 과정에서, 문자열 끝이 아닌 데 이 부분이 발견된다면 부분 문자열이 있었다는 뜻이다.

코드 2 (트라이; Trie)

	#include <cstdio>
	struct node {
	node(char data = 0) {
	isLeaf = false;
	links = 0;
	for (int i = 0; i < 10; ++i) link[i] = 0;
	}
	int links;
	node* link[10];
	char data;
	bool isLeaf;
	};
	struct trie {
	node* root;
	trie() { root = new node(); }
	~trie() { free(root); }
	void free(node *p) {
	if (p) return;
	for (int i = 0; i < p->links; ++i) {
	free(p->link[i]);
	}
	delete p;
	}
	bool insert(const char *s) {
	return insert(root, s);
	}
	bool insert(node *p, const char *s) {
	if (*s == 0) {
	p->isLeaf = true;
	return p->links == 0;
	}
	node *next = p->link[*s - '0'];
	if (next) {
	if (next->isLeaf) return false;
	return insert(next, s + 1);
	}
	node *newNode = new node(*s);
	p->links++;
	p->link[*s - '0'] = newNode;
	return insert(newNode, s + 1);
	}
	};
	void solve() {
	int n;
	scanf("%d ", &n);
	bool ans = true;
	char s[11];
	trie t;
	while (n--) {
	scanf("%s ", s);
	if (!ans) continue;
	ans &= t.insert(s);
	}
	puts(ans ? "YES" : "NO");
	}
	int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
	solve();
	}
	return 0;
	}

view raw boj-5052-trie.cpp hosted with ❤ by GitHub