[BOJ] 5052 전화번호 목록

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

 

 

동적 할당 방식

#include <iostream>
using namespace std;

const int TrieNode = 10;

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

	Trie() {
		fill(next, next + TrieNode, nullptr);
		finish = nextChild = false;
	}
	~Trie() {
		for (int i = 0; i < TrieNode; i++) {
			if (next[i]) delete next[i];
		}
	}
	bool insert(const char* key) {
		if (*key == '\0') {
			finish = true;
			return !nextChild;
		}
		nextChild = true;
		
		int nextKey = *key - '0';
		if (!next[nextKey]) next[nextKey] = new Trie();

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

		return !finish && get;
	}
};
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	int tc;
	cin >> tc;

	while (tc--)
	{
		int n;
		cin >> n;

		// 트라이의 루트 생성
		Trie *root = new Trie;

		bool chk = true;

		for (int i = 0; i < n; i++)
		{
			char phone[11];
			cin >> phone;

			// 일관성이 없다면
			if (chk && root->insert(phone) == 0)
				chk = false;
		}

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

		// 트라이 소멸
		delete root;
	}


	return 0;
}

 

 

정적 할당 방식

#include <iostream>
#include <string.h>
using namespace std;
const int NEXTMAX = 10; // 트라이 노드마다 포인터 개수
const int NUMMAX = 100001; // 트라이의 최대 글자 개수


int tc, n;

struct trie {
	int cnt; // 노드의 개수
	int next[NUMMAX][NEXTMAX];
	bool finish[NUMMAX];
	bool child[NUMMAX];

	trie() {
		cnt = 1;
		memset(next, 0, sizeof(next));
		memset(finish, 0, sizeof(finish));
		memset(child, 0, sizeof(child));
	}
	bool insert(const char* key, int node = 0) {
		if (*key == '\0') {
			finish[node] = true;
			return !child[node];
		}
		int nextN = *key - '0';
		if (!next[node][nextN]) next[node][nextN] = cnt++;
		child[node] = true;
		bool get = insert(key + 1, next[node][nextN]);
		return !finish[node] && get;
	}
};

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

	cin >> tc;
	while (tc--) {
		cin >> n ;
		bool res=true;
		trie t;
		for (int i = 0; i < n; i++) {
			char phoneN[11];
			cin >> phoneN;
			if (res && !t.insert(phoneN)) res = false;
		}
		if (res) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

 

 

정렬을 이용한 풀이

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int tc, n;
vector<string> v;

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

	cin >> tc;
	while (tc--) {
		cin >> n;
		v.clear();
		for (int i = 0; i < n; i++) {
			string s;
			cin >> s;
			v.push_back(s);
		}
		sort(v.begin(), v.end());
		bool chk = true;
		for (int i = 0; i < n-1; i++) {
			if (v[i] == v[i + 1].substr(0, v[i].size())) {
				chk = false;
				break;
			}
		}
		if (chk) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

 

시간 비교

1번 - 동적 할당

2번 - 정적 할당

3번 - 정적 할당 코드에서 trie *t=new trie; 한 것

4번 - 정렬 이용