백준 5052번, 전화번호 목록

문제

백준 5052번

풀이

문자열 $ A $가 다른 문자열의 접두사인지 빠르게 확인해야 합니다.

입력 받은 전화번호를 모두 정렬해봅시다.

 

911
97625999
91125426

이 케이스를 정렬하면

911
91125426
97625999

이렇게 됩니다.

 

여기서 관찰할 수 있는 것은, 문자열 $ A $가 임의의 문자열 $ B $의 접두사가 된다면, 그러한 문자열 $ B $는 항상 $ A $ 바로 뒤에 있다는 것입니다.

 

이 말이 이해가 안된다면 사전을 생각해봅시다.

"abcd", "abcde"와 같은 단어가 있다고 가정합시다.

이를 사전순으로 배열하면 "abcd"까지 같으니 더 긴 문자열이 뒤로 오게 됩니다.

그렇게 뒤에 온 문자열은 항상 앞의 문자열을 접두사로 포함하고 있는 꼴이 될 것 입니다.

 

마지막으로 정리하면 문자열을 정렬한 뒤, 모든 $ i\ (1 \leq i \lt N) $에 대해서 $ A_{i} $는 $ A_{i + 1} $의 접두사의 후보가 될 수 있습니다.

 

따라서, 인접한 문자열만 확인해주면 $ O(TNlogN) $에 풀 수 있습니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

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

	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		cin.ignore();
		vector<string> vec;
		while (n--) {
			string str; getline(cin, str);
			vec.push_back(str);
		}
		sort(all(vec));
		int f = 0;
		for (auto it = vec.begin(); it < vec.end() - 1; ++it) {
			if ((it + 1)->find(*it) == 0) {
				f = 1;
				break;
			}
		}
		cout << (f ? "NO" : "YES") << "\n";
	}
}