[5052] 전화번호 목록

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

5052번: 전화번호 목록

입력된 전화번호를 전부 set에 넣는다.

set을 전부 순회하는 첫번째 for(i)에 대해서, i의 다음것부터 substring끼리 비교해주었다.

else if (cur < nxt) break;

위 문장이 없으면 TLE가 나온다. 제한시간이 1초인 문제에서, n=10000일때 N^2의 순회에, set의 상수까지 생각하면

시간초과에 꽤 유의해야 할 듯 싶으나, 정작 접두어만을 확인할때, 불필요한 부분을 사전순 비교로 잘라내면 

전체적으로 꽤 빠른 시간안에 들어온다.

수기로 비교할때, 정작 데이터의 양에 비해서 확인할 대상이 많지 않음에 주목하고, 적절히 잘라내자.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

set<string> st;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    int t;

    cin >> t;

    while (t--) {

        int n;

        cin >> n;

        st.clear();

        int i;

        bool flag = true;

        for (i = 0; i < n; i++) {

            string s;

            cin >> s;

            st.insert(s);

        }

        for (auto it = st.begin(); it != st.end(); it++) {

            string cur = *it;

            if (next(it) == st.end()) break;

            for (auto nit = next(it); nit != st.end(); nit++) {

                string nxt = *nit;

                if (cur.length() > nxt.length()) continue;

                nxt = nxt.substr(0, cur.length());

                if (cur == nxt) {

                    flag = false;

                    goto findAns;

                } else if (cur < nxt)

                    break;

            }

        }

    findAns:

        cout << (flag ? "YES" : "NO") << '\n';

    }

    return 0;

}

---