07. 정렬 문제 [BOJ 5052번]

1. 관련 문제 🎯

문제 : 백준 5052 전화번호 목록 ☎️
난이도 : 골드 4

2. 문제 소개 🧩

1️⃣ 전화번호의 길이는 최대 10자리이다.
2️⃣ 목록에 있는 두 전화번호가 같은 경우는 없다.
3️⃣ 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
4️⃣ 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

• 아래에서 첫번째 예시를 살펴보면, 총 3개의 전화번호(911, 97625999, 91125426)가 주어진다.
  이때, 911은 91125426의 접두어가 되므로 이 전화번호 목록은 일관성이 없는 목록이다.
• 아래에서 두번째 예시를 살펴보면, 총 5개의 전화번호(113, 12340, 123440, 12345, 98346)이 주어진다. 이때, 한 번호가 다른 번호의 접두어가 되는 경우가 없으므로 해당 전화번호 목록은 일관성 있는 목록이다.
  

3. 문제 풀이 🖌️

3-1. 하나의 전화번호 목록에 전화번호를 입력받는다.

string phoneNumber;
vector<string> number;
for(int i=0; i<n; i++){
	cin>>phoneNumber;
    number.push_back(phoneNumber);
}

3-2. 전화번호 목록을 정렬한다.

• 이때, 문자열을 정렬한다는 것을 가장 주목해야 한다!!
• 숫자를 정렬하는 경우에는 큰 순서대로 비교하여 오름차순으로 정렬한다.
  ex) 1233, 9999, 12345, 123440
• 그러나, 문자열을 정렬하는 경우에는 첫번째 문자부터 문자의 순서를 비교하여 정렬한다. -> 문자열이 맨 앞이 동일하게 정렬이 된다. 따라서 전화번호의 앞 뒤로만 살펴보면 되어서 접두어가 있는지를 빠르게 확인할 수 있다.
  ex) "1233", "123440", "12345", "9999"

sort(number.begin(), number.end());

3-3. 한 번호가 다른 번호의 접두어인 경우가 있는지 확인한다.

• 하나의 번호 number[i]를 기준으로 다른 번호들(number[j])의 접두어인지를 살펴본다.

한 번호가 다른 번호의 접두어가 되려면, 다음의 조건을 만족해야 한다.

• 1) 해당 번호가 다른 번호보다 짧아야 한다.
  -> 따라서, number[i].size() > number[j].size()인 경우 break
  ex) 911, 91123
• 2) 해당 번호의 맨 앞자리와 다른 번호의 맨 앞자리가 동일해야 한다.
  -> number[i][0] != number[j][0]인 경우 break
  ex) 911, 91123
• 3) 해당 번호가 다른 번호의 접두어인지 확인한다.
  -> number[j]를 number[i]만큼 잘라서 동일하다면 접두어이다!

string ans = "YES";

for(int i = 0; i < n; i++){
	for(int j=i+1; j<n; j++){
    	if(number[i].size() > number[j].size()) break;
        if(number[i][0] != number[j][0])    break;
        if(number[i] == number[j].substr(0, number[i].size())){
        	ans = "NO";
            break;
        }	//한 번호가 다른 번호의 접두어인 경우
    }
    if(ans == "NO") break;
}

4. 전체 코드 🔑

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    int t = 0;  //테스트 케이스 수
    int n = 0;  //전화번호 수
    cin>>t;

    while(t--){
        cin>>n;
        string phoneNumber;
        vector<string> number;
        for(int i=0; i<n; i++){
            cin>>phoneNumber;
            number.push_back(phoneNumber);
        }

        sort(number.begin(), number.end());

        string ans = "YES";

        for(int i = 0; i < n; i++){
            for(int j=i+1; j<n; j++){
                if(number[i].size() > number[j].size()) break;
                if(number[i][0] != number[j][0])    break;
                if(number[i] == number[j].substr(0, number[i].size())){
                    ans = "NO";
                    break;
                }
            }
            if(ans == "NO") break;
        }

        cout<<ans<<"\n";
    }
}

5. 결과 🏆