[C++] 백준 5052번 - 전화번호 목록

생각보다 생각을 많이 해야했던 문제이다.

코테는 항상 문제를 잘 분석하는 것에서부터 시작한다.

 

1. 항상 문제를 잘 읽어야 한다

 

문제에 낚시가 있었는데, 그것을 긴급번호로 쓰여진 것이었다.

그러니까 당연히 긴급번호가 처음으로 들어오고 그 번호를 기준으로 substr을 하면 되는줄 알고 계속 틀렸었다.

그러나 문제는 긴급번호가 기준이 아닌 모든 전화번호를 기준으로 문제를 풀어야한다

 

ex)

11240

48298405824

113

113134

NO

 

즉, 첫 번째에 상관없이 어떤 전화번호가 다른 전화번호의 전화번호가 되면 안된다는 것이다.

 

2. 빠른 탐색을 위해 sort를 통해서 vector를 정렬시키고, length를 비교해서 current가 next보다 길면 넘겨버렸다

접두사라는 개념을 생각하면, current string이 next string보다 길면 안된다.

 

생각해야되는 부분은 이 두 개인 것 같다.

다른 사람들은 '트라이'라는 자료구조를 사용했다고 하는데

이 부분에 대해서는 또 공부를 해봐야 할 것 같다.

 

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

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

	int t; cin >> t;

	for (int i = 0; i < t; i++) {
		int n;
		cin >> n;
		string s;
		vector<string> v;
		for (int j = 0; j < n; j++) {
			cin >> s;
			v.emplace_back(s);
		}
		sort(v.begin(), v.end());
		bool check = true;
		for (int j = 0; j < v.size() - 1; j++) {
			string current = v[j];
			string next = v[j + 1];

			if (current.size() > next.size())
				continue;
			if (current == next.substr(0, current.length())) {
				check = false;
				break;
			}
		}
		if (check)
			cout << "YES\n";
		else
			cout << "NO\n";
	}


	return 0;
}