[백준 5052] 전화번호 목록

트라이로 품

 

 

그리고 정렬하고 트라이에 넣어야함

왜냐하면 9114 911 이렇게 들어가면

911 들어갈때 일관성 검사를 못하기 때문

 

길이가 짧은 것부터 넣어야함

그래야 일관성 검사가 가능

 

---

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

using namespace std;

typedef struct _Node {
	struct _Node* childs[10] = { NULL, };
	bool isWord = false;
}Node;

// 트라이 추가 함수
bool insert(Node* root, string s) {
	Node* cur = root;

	int idx;
	for (int i = 0; i < s.size(); i++) {
		idx = s[i] - '0';

		if (cur->childs[idx] == NULL) {
			cur->childs[idx] = new Node();
		}

		cur = cur->childs[idx];

		// 가던 길에 단어인 놈이 있으면 일관성 없는거임
		if (cur->isWord) {
			return false;
		}
	}

	cur->isWord = true;

	return true;
}

bool compare(string s1, string s2) {
	return s1.size() < s2.size();
}

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

	int T, N;
	string s;

	cin >> T;
	for (int i = 0; i < T; i++) {
		
		Node* root = new Node();
		vector<string> v;
		cin >> N;
		for (int k = 0; k < N; k++) {
			cin >> s;
			v.push_back(s);
		}
		
		// 길이 작은 순으로 정렬
		sort(v.begin(), v.end(), compare);

		bool isCorrect = true;
		for (int i = 0; i < v.size(); i++) {
			isCorrect = insert(root, v[i]);
			if (!isCorrect) break;
		}

		if (isCorrect) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}

	return 0;
}

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef struct _Node {
	struct _Node* childs[10] = { NULL, };
	bool isWord = false;
}Node;

// 트라이 추가 함수
void insert(Node* root, string s) {
	Node* cur = root;

	int idx;
	for (int i = 0; i < s.size(); i++) {
		idx = s[i] - '0';

		if (cur->childs[idx] == NULL) {
			cur->childs[idx] = new Node();
		}

		cur = cur->childs[idx];
	}

	cur->isWord = true;
}

// 중복 확인 함수
bool check(Node* root, string s) {
	Node* cur = root;

	int idx;
	for (int i = 0; i < s.size()-1; i++) {
		idx = s[i] - '0';

		cur = cur->childs[idx];

		if (cur->isWord) return false;
	}

	return true;
}

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

	int T, N;
	string s;

	cin >> T;
	for (int i = 0; i < T; i++) {
		
		Node* root = new Node();
		vector<string> v;
		cin >> N;
		for (int k = 0; k < N; k++) {
			cin >> s;
			v.push_back(s);
			insert(root, s);
		}

		bool isCorrect = true;

		for (int k = 0; k < N; k++) {
			isCorrect = check(root, v[k]);
			if (!isCorrect) break;
		}

		if (isCorrect) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}

	return 0;
}