단어 입력 순서대로 두개씩 비교한다. 맨 앞 알파벳부터 비교한다. 같으면 다음 알파벳으로 넘어가고 다르면 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
와 같은 모순되는 입력이 들어오는 경우, ‘!’를 출력하고 바로 종료해야한다.