[Algorithm]Baekjoon 5052번 :: 전화번호 목록

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
 
int t, n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
 
    cin >> t;
 
    while (t--)
    {
        cin >> n;
 
        vector<string> nums;
 
        for (int i = 0; i < n; ++i)
        {
            string s;
            cin >> s;
 
            nums.push_back(s);
        }
 
        sort(nums.begin(), nums.end());
        
        bool check = false;
 
        for (int i = 0; i < nums.size()-1; ++i)
        {
            if (nums[i].size() <= nums[i+1].size())
            {
                if (nums[i] == nums[i + 1].substr(0, nums[i].size()))
                {
                    check = true;
                    break;
                }
            }
        }
 
        if (check)
        {
            cout << "NO" << endl;
        }
        else
        {
            cout << "YES" << endl;
        }
    }
}
 
 

 

 

주어진 문자열들중에서, 어떤 문자열이 다른 문자열의 접두어부분과 똑같을 경우 NO를 출력하고, 아니면 YES를 출력하면 된다.

 

이 문제같은경우는 정렬시켜주면 굉장히 쉽게 풀 수 있는 문제이다.

정렬할 경우 사전순으로 정렬이 되어지는데, 그러면 그냥 현재문자열의 크기만큼 다음문자열의 0번째인덱스부터 비교를 해주면 된다.