문제 설명
여러 개의 단어로 이루어진 배열이 주어졌을 때, 영어 알파벳의 임의의 순서를 하나 정해서 주어진 단어들이 오름차순으로 정렬된 것처럼 보이도록 만들 수 있는 알파벳 순서를 찾아야 합니다. 조건을 만족하는 순서가 존재하면 그 순서를 출력하고, 어떤 순서로도 정렬이 불가능하다면 "Impossible"을 반환합니다.
예를 들어 입력이 words = ["efgh", "wxyz"]라면, 출력은 zyxvutsrqponmlkjihgfewdcba가 됩니다.
해결 접근 방법
이 문제는 그래프 이론의 위상 정렬(Topological Sorting)을 활용하면 효율적으로 해결할 수 있습니다. 인접한 두 단어를 비교하여 처음으로 다른 문자가 나타나는 지점에서 "앞 문자가 뒤 문자보다 먼저 와야 한다"는 선행 관계를 그래프의 간선으로 기록하고, 이렇게 만들어진 그래프에 대해 위상 정렬을 수행하면 조건을 만족하는 알파벳 순서를 얻을 수 있습니다.
구체적인 해결 단계는 다음과 같습니다.
- ALPHABET := 26 (알파벳 문자 수)
- n := 단어 배열 v의 크기
- 만약 n이 1이라면 제약 조건이 없으므로 "abcdefghijklmnopqrstuvwxyz"를 출력하고 종료
- 크기가 ALPHABET인 인접 리스트 배열 adj를 정의
- 크기가 ALPHABET이고 0으로 초기화된 진입 차수 배열 in을 정의
- pre := v[0]
- i := 1부터 i < n까지 반복:
- s := v[i]
- j를 0부터 min(pre의 길이, s의 길이) - 1까지 반복하며 s[j]와 pre[j]가 서로 다른 첫 번째 위치를 찾음
- 다른 문자를 찾았다면(j < min(pre의 길이, s의 길이)):
- adj[pre[j] - 'a']의 끝에 s[j] - 'a'를 추가하여 간선 생성
- in[s[j] - 'a'] 값을 1 증가
- pre := s로 갱신한 뒤 다음 반복으로 진행
- 다른 문자를 찾지 못했는데 pre의 길이가 s보다 길다면(예: "abc" 다음에 "ab"가 오는 경우) 올바른 순서가 존재하지 않으므로 "Impossible"을 출력하고 종료
- pre := s로 갱신
- 스택 my_stack을 정의하고, 진입 차수가 0인 모든 문자를 스택에 삽입
- 결과를 저장할 배열 out과 방문 여부를 기록하는 크기 26의 배열 vis(false로 초기화)를 정의
- 스택이 빌 때까지 반복:
- x := 스택의 최상위 요소를 꺼냄(pop)
- vis[x] := true로 설정
- out의 끝에 x + 'a' 추가
- adj[x]의 모든 인접 노드에 대해:
- 이미 방문한 노드라면 건너뜀
- in[adj[x][i]] 값을 1 감소
- 감소 후 진입 차수가 0이 되면 해당 노드를 스택에 삽입
- 모든 문자를 확인했을 때 방문하지 않은 문자가 남아 있다면 사이클이 존재한다는 의미이므로 "Impossible"을 출력하고 종료
- out에 저장된 문자들을 순서대로 출력
예제 구현
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define ALPHABET 26
void search_ordering(vector<string> v) {
int n = v.size();
if (n == 1) {
cout << "abcdefghijklmnopqrstuvwxyz";
return;
}
vector<int> adj[ALPHABET];
vector<int> in(ALPHABET, 0);
string pre = v[0];
for (int i = 1; i < n; ++i) {
string s = v[i];
int j;
for (j = 0; j < min(pre.length(), s.length()); ++j)
if (s[j] != pre[j])
break;
if (j < min(pre.length(), s.length())) {
adj[pre[j] - 'a'].push_back(s[j] - 'a');
in[s[j] - 'a']++;
pre = s;
continue;
}
if (pre.length() > s.length()) {
cout << "Impossible";
return;
}
pre = s;
}
stack<int> my_stack;
for (int i = 0; i < ALPHABET; ++i)
if (in[i] == 0)
my_stack.push(i);
vector<char> out;
bool vis[26];
memset(vis, false, sizeof(vis));
while (!my_stack.empty()) {
char x = my_stack.top();
my_stack.pop();
vis[x] = true;
out.push_back(x + 'a');
for (int i = 0; i < adj[x].size(); ++i) {
if (vis[adj[x][i]])
continue;
in[adj[x][i]]--;
if (in[adj[x][i]] == 0)
my_stack.push(adj[x][i]);
}
}
for (int i = 0; i < ALPHABET; ++i)
if (!vis[i]) {
cout << "Impossible";
return;
}
for (int i = 0; i < out.size(); ++i)
cout << out[i];
}
int main() {
vector<string> v{"efgh", "wxyz"};
search_ordering(v);
}입력
{"efgh", "wxyz"}출력
zyxvutsrqponmlkjihgfewdcba
정리
이 알고리즘의 시간 복잡도는 단어 비교에 O(총 문자 수), 위상 정렬에 O(26 + E)로 전체적으로 매우 효율적입니다. 특히 진입 차수가 0이 된 노드부터 처리하는 칸(Kahn) 알고리즘 방식을 사용하기 때문에, 그래프에 사이클이 존재하는 경우에도 방문하지 못한 문자가 남게 되어 이를 자연스럽게 검출할 수 있다는 장점이 있습니다.