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

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

풀이

먼저 입력받은 배열을 정렬한 후에 비교를 진행하고자 했다.

처음엔 입력받은 숫자들을 크기순으로 정렬해야 된다고 생각해서 별도의 정렬 함수를 추가했었다.

하지만 크기순으로 정렬을 하게되면 겹치는 숫자끼리 멀어질 수 있기 때문에 기본 정렬을 해야한다.

예를 들어, 113 12340 123406 12345 98576이 입력값으로 주어졌을 경우

string의 기본 정렬을 진행하게 되면 113 12340 123406 12345 98576 순으로 정렬이 된다.

이 경우에는 12340이 다음 원소인 123406의 접두어이기 때문에 "NO"를 출력하게 된다.

하지만 크기순으로 정렬을 하게되면 113 12340 12345 123406 98576 순으로 정렬이 되기 때문에

12340과 123406이 서로 멀어져 "YES"를 출력하게 된다.

이렇게 될 경우 모든 원소값들을 검사하기 위해 이중 반복문을 사용해야 하는데 그럴 경우 시간복잡도도

커지고 코드가 복잡해진다. 따라서 기본 정렬을 진행해서 각 원소와 그 다음 원소의 값만 비교하도록 했다.

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

using namespace std;

int main() {
	int t, n;
	string phone_num;
	vector<string> answer;
	bool flag;
	cin >> t;
	for (int i = 0; i < t; i++) {
		flag = true;
		vector<string> phone;
		cin >> n;
		for (int j = 0; j < n; j++) {
			cin >> phone_num;
			phone.push_back(phone_num);
		}
		sort(phone.begin(), phone.end());
		for (int j = 0; j < phone.size() - 1; j++) {
			if (phone[j] == phone[j+1].substr(0,phone[j].size())) {
				flag = false;
				break;
			}
		}
		if (flag)
			answer.push_back("YES");
		else
			answer.push_back("NO");
	}
	for (string elem : answer)
		cout << elem << "\n";
}