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

문제링크 : https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int t, n;
bool flag;
vector<string>v;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> t;
    while(t--)
    {
        flag = 1; v.clear();
        cin >> n;
        while(n--)
        {
            string s;
            cin >> s;
            v.push_back(s);
        }

        sort(v.begin(), v.end()); //정렬

        for(int i=0; i<v.size()-1; i++)
        {
            int cur = v[i].size(); //현재 문자열
            int next = v[i+1].size(); //바로 다음 문자열
            if(cur>=next) continue;

            if(v[i+1].substr(0, cur)==v[i]) flag = 0; //다음 문자열에 현재 문자열이 부분적으로 포함되어있는가?
        }

        cout << (flag == 1 ? "YES" : "NO") << "\n";
    }
    
}

 

입력받은 문자열을 정렬하여 벡터에 저장하고 이를 각각 비교하여 풀 수 있는 문제이다.

한 번호가 다른 번호의 접두어(부분 포함)인지 확인해야 하므로 벡터를 정렬해준다.

 

이후 반복문에서 현재 문자열과 바로 다음 문자열을 비교해주는데,

만약 현재 문자열의 길이가 다음 문자열의 길이보다 길거나 같다면 접두어가 불가능한 케이스이므로 스킵해준다.

 

substr을 통해서 다음 문자열 부분 문자열(처음~현재 문자열의 길이)이 현재 문자열과 같은 지를 확인하고 같다면 일관적이지 않은 경우이다.

이를 판별하기 위해 flag 변수를 사용하여 일관적인지 아닌지를 체크하는 용도로 사용한다.

 

풀고 나서 다른 풀이를 보니 트라이라는 자료구조로 푸는 방법도 볼 수 있었다.

아에 처음 접하는 것이고 간단하게 훝어봤을 때 조금 복잡해보였는데 다음에 한번 시도해봐야겠다.