알고스팟어

백준 2848번: 알고스팟어

아이디어

단어 입력 순서대로 두개씩 비교한다. 맨 앞 알파벳부터 비교한다. 같으면 다음 알파벳으로 넘어가고 다르면 string1[i]->string2[i] 간선을 만들어준 후 다음 단어로 넘어간다. 그래프가 만들어지면 위상정렬 후 출력한다. 이 때 입력된 모든 알파벳을 다 사용하지 않은 경우 ‘!’를 출력하고, 중간에 큐 사이즈가 1보다 커지면 가능한 순서가 여러개이므로 ‘?’을 출력한다.

코드

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    vector<string> v(n);
    vector<vector<int>> adj(26);
    bool cnt[26] = {0}; // 사용중인 알파벳 체크
    int sz = 0; // 총 알파벳 개수
    int indegree[26] = {0};

    for (int i = 0; i < n; i++) {
        cin >> v[i];
        for (char c : v[i]) {
            if (!cnt[c-'a']) {
                sz++;
                cnt[c-'a'] = true;
            }
        }
    }

    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < 10; j++) {
            if (v[i].size() == j || v[i+1].size() == j) {
                // 2 ab a 처럼 모순되는 순서로 입력되면 '!' 출력 후 종료
                if (v[i+1].size() == j && v[i].size() > j) {
                    cout << '!';
                    return 0;
                }
                break;
            }
            if (v[i][j] != v[i+1][j]) {
                adj[v[i][j]-'a'].push_back(v[i+1][j]-'a');
                indegree[v[i+1][j]-'a']++;
                break;
            }
        }
    }

    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] && !indegree[i]) q.push(i);
    }

    string ans;
    bool sw = false;

    while (!q.empty()) {
        if (q.size() > 1) sw = true;
        int cur = q.front();
        q.pop();
        ans += (char)(cur+'a');
        for (int next : adj[cur]) {
            if (cnt[next] && !(--indegree[next])) q.push(next);
        }
    }

    // 완성 안되면 '!' / 중간에 큐 사이즈가 1보다 큰 경우는 가능한 순서가 한 개 이상이므로 '?'

    if (ans.size() != sz) cout << '!';
    else if (sw) cout << '?';
    else cout << ans;

    return 0;
}

여담

2
ab
a
와 같은 모순되는 입력이 들어오는 경우, ‘!’를 출력하고 바로 종료해야한다.