백준 5052. 전화번호 목록 - 문제풀이 (c++) (문자열)

🔎 5052. 문제 보기

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

---

💡 문제 풀기 전

입력 예시

911
97625999
91125426

또는
91125426
911
97625999

---

위의 입력 예시를 보면 이 문제는 입력 순서에 구애받지 않고, 모두 탐색해서 비교를 해야 한다. 그래서 처음에는 모두 하나하나 비교하는 n^2(n은 10000)을 떠올렸지만 시간제한이 1초이므로 O(n^2)로는 어림도 없었다. 그래서 nlog(n)으로 탐색하는 방법을 찾으려 했다.

📝 코드 보기

1. 정렬해서 다음인덱스와 비교하기

#include <bits/stdc++.h>
using namespace std;

int main() {
	int tc;
	string str;
	cin >> tc;
	while(tc--) {
		int n;
		cin >> n;
		vector<string> book;
		for(int i=0; i<n; i++) {
			cin >> str;
			book.push_back(str);
		}
		
		sort(book.begin(), book.end());
		
		bool flag=false;
		for(int i=0; i<n-1; i++) {
			string a=book.at(i), b=book.at(i+1);

			if(a.size()>=b.size()) continue;
			if(a==b.substr(0, a.size())) {
				cout << "NO" << "\n";
				flag= true;
				break;
			}
		}
		if(!flag) cout <<"YES" << "\n";
	}
	
	return 0;
}

---

2. 사전을 이용해 찾는 방법(Map)

#include <bits/stdc++.h>
using namespace std;

int main() {
	int tc;
	cin >> tc;
	while(tc--) {
		int n;
		string str;
		cin >> n;
		vector<string> v;
		map<string, int> book;
		
		for(int i=0; i<n; i++) {
			cin >> str;
			v.push_back(str); // 사전에서 찾기 위해서 
			book[str]=1; // 사전에 저장 
		}
		
		bool flag=true;
		for(int i=0; i<n; i++) {
			if(!flag) break;
			
			string temp="";
			for(int j=0; j<v[i].length(); j++) {
				temp+=v[i][j];
				if(book[temp]==1 && temp!=v[i]) {
					flag=false;
					break;
				}
			}
		}
		
		if(flag) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}
	
	return 0;
}

---

3. 트라이(TRIE)

이 코드를 보기전에 문자열 포인터 이 링크를 먼저 보고 문자열 포인터에 대해 이해하자.

#include <bits/stdc++.h>
using namespace std;

struct Trie {
	Trie *node[10];
	bool finish;
	Trie() {
		finish=false;
		for(int i=0; i<10; i++) {
			node[i]=NULL;
		}
	}
	
	void insert(char *str) {
		if(*str==NULL) {
			finish=true;
			return;
		}
		int cur = *str-'0';
		if(node[cur] == NULL) node[cur] = new Trie();
		node[cur]->insert(str+1);
	}
	
	bool find(char *str) {
		if(*str==NULL) {
			return false;
		}
		
		if(finish==true) {
			return true;
		}
		
		int cur = *str-'0';
		if(node[cur]==NULL) return false;
		return node[cur]->find(str+1);
	}
};

char input[100000][11];
vector<string> book;

int main() {
	int tc;
	cin >> tc;
	while(tc--) {
		int n;
		string str;
		cin >> n;
		Trie *root = new Trie();
		for(int i=0; i<n; i++) {
			cin >> input[i];
			book.push_back(input[i]);
			root->insert(input[i]);
		}
		for(int i=0; i<n; i++) {
			if(root->find(input[i])) {
				cout << "NO\n";
				break;
			}
			else if(i==n-1) {
				cout << "YES\n";
			}
		}
	}
}

---

🎈 코드 풀이 및 관련 개념

트라이
트라이 장점: 탐색할 때 시간 복잡도: log(n)
트라이 단점: 메모리를 많이 차지함.