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

문제

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

 

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

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

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

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

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

 

입력된 전화번호 목록에 대해 일관성이 있으면 YES, 없으면 NO를 출력하면 되는 문제이다. 

목록에 똑같은 전화번호가 두 개 이상 존재하지 않는다. 

풀이

입력된 전화번호 목록을 정렬하게 되면, 

정렬된 상태에서는 

i번째 전화번호가 i+1번째 전화번호의 접두어가 아니면, 해당 목록은 일관성이 있는 목록이다. 

-> 정렬된 상태에서는 i번째와 i+1번째의 관계에 대해서만 검사해주면 된다는 것이다 ! 

 

이렇게되면 반복 횟수가 확 줄게 된다. 

 

접두어인지 여부는, 

i+1번째 전화번호의 0번째 자리부터 i번째 전화번호의 길이 만큼 substr을 해서, 해당 substr이 i번째 전화번호와 같은지 비교하면 된다.

코드

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

using namespace std;


int main() {
	int T, N;
	cin >> T;
	for (int t = 0;t < T;t++) {
		cin >> N;
		vector<string> numbers;
		for (int n = 0;n < N;n++) {
			string temp;
			cin >> temp;
			numbers.push_back(temp);
		}
        //정렬
		sort(numbers.begin(), numbers.end());
		string before = numbers[0];
		string now;
		bool isOk = true; // 일관성이 있는 목록인지 여부
		for (int n = 1;n < N;n++) {
			now = numbers[n];
			// before가 now에 속하는지 확인 (before가 now의 접두어인지)
			if (now.substr(0, before.size()) == before) {
				isOk = false;
				break;
			}
			before = now; // before 갱신
		}
		if (isOk) cout << "YES" <<endl;
		else  cout << "NO" << endl;
	}
}

결과

 

참고 

 

B+ tree로 풀 수 있는 문제라고 한다! -> 이게 정석 방식인듯