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

문제 링크

5052번: 전화번호 목록

 

풀이

문자열 문제. 처음에는 완탐으로 했는데 시간초과가 나길래.. 찾아보았다.
정렬하는 것까진 맞았는데, 정렬을 하게 되면 바로 뒤에꺼만 확인하면 된다. 하하

1. 문자열을 입력받고 정렬한다.
2. 현재 문자열을 기준으로 다음 문자열을 substr로 잘라서 같은지 확인한다.
3. 같으면 NO, 전체 확인이 끝나도 flag가 true라면 YES를 출력한다.

 

코드

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        vector<string> arr(n);
        for (int j = 0; j < n; j++)
        {
            cin >> arr[j];
        }

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

        bool flag = true;
        for (int j = 0; j < n-1; j++)
        {
            string cur = arr[j];
            string next = arr[j + 1].substr(0, cur.size());
            if (cur == next)
            {
                cout << "NO\n";
                flag = false;
                break;
            }
        }
        if (flag)
        {
            cout << "YES\n";
        }
    }

}