BOJ. Phone Number List (5052)

Problem: BOJ 5052 — Phone Number List · 한국어 · 日本語

Sort all phone numbers in lexicographic order, then inspect each adjacent pair. If one number is a prefix of another, the shorter number sorts immediately before the longer one: at the first position after the shorter number ends, the longer one still has a digit, which makes it sort later. Thus any prefix conflict appears in an adjacent pair. Equal strings also count as a prefix conflict, and the prefix comparison below correctly detects them.

The list is rebuilt for every test case, so no number or conflict state carries over between cases. The sort takes O(N log N * L) time when comparing strings of maximum length L; the adjacent scan takes O(NL). Storing the numbers takes O(NL) space.

C++17

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int test_cases;
    cin >> test_cases;

    while (test_cases--) {
        int n;
        cin >> n;

        vector<string> numbers(n);
        for (string& number : numbers) {
            cin >> number;
        }

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

        bool consistent = true;
        for (int i = 0; i + 1 < n; ++i) {
            if (numbers[i + 1].compare(0, numbers[i].size(), numbers[i]) == 0) {
                consistent = false;
                break;
            }
        }

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