Leetcode 269. Alien Dictionary

문제

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language.

If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "".

Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there are multiple solutions, return any of them.

새로운 외계 언어가 있으며, 이 언어는 영어 알파벳을 사용합니다. 하지만 알파벳 문자의 순서는 알려져 있지 않습니다.

외계 언어 사전에 있는 문자열 목록 words가 주어집니다. words의 문자열들은 이 외계 언어의 규칙에 따라 사전순으로 정렬되어 있다고 주장합니다.

이 주장이 잘못되었으며, words의 현재 배열 순서를 만족하는 알파벳 순서가 존재하지 않는다면 빈 문자열 ""을 반환하세요.

그렇지 않다면, 외계 언어에 등장하는 모든 고유 문자를 해당 언어의 사전순으로 정렬한 문자열을 반환하세요. 가능한 정답이 여러 개라면 그중 아무거나 반환해도 됩니다.

---

예시

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

---

제한

• $1 <= words.length <= 100$
• $1 <= words[i].length <= 100$
• words[i] 는 영어 소문자로만 구성된다.

---

풀이

이 문제는 문자 사이의 선후 관계를 그래프로 만든 뒤, 위상 정렬을 수행하는 문제입니다.

1. 모든 고유 문자를 그래프에 추가한다

정답에는 words에 등장하는 모든 문자가 포함되어야 합니다.

따라서 문자 간의 순서 관계가 없더라도, 각 문자를 그래프의 정점으로 먼저 추가합니다.

2. 인접한 두 단어를 비교해 문자 순서를 찾는다

사전순으로 정렬된 두 단어를 비교할 때, 두 단어에서 처음으로 서로 다른 문자가 순서를 결정합니다.

예를 들어 다음 두 단어가 있다고 가정합니다.

wrt
wrf

앞의 w, r은 같고 마지막 문자가 t, f로 다릅니다.

wrt가 wrf보다 앞에 있으므로 외계 언어에서는 다음 관계가 성립합니다.

t → f

즉, t가 f보다 먼저 등장해야 한다는 의미입니다.

각 인접한 단어 쌍을 비교하면서 처음으로 다른 문자를 발견하면 다음과 같이 처리합니다.

• 앞 단어의 문자에서 뒤 단어의 문자로 간선을 추가한다.
• 뒤 문자의 진입 차수를 1 증가시킨다.
• 첫 번째로 다른 문자 이후의 문자들은 사전순에 영향을 주지 않으므로 비교를 종료한다.

3. 잘못된 접두사 관계를 확인한다

두 단어에서 다른 문자를 찾지 못했다면, 한 단어가 다른 단어의 접두사라는 뜻입니다.

사전순에서는 짧은 단어가 긴 단어보다 먼저 나와야 합니다.

따라서 다음과 같은 순서는 올바를 수 없습니다.

["abc", "ab"]

앞 단어가 뒤 단어보다 길면서 뒤 단어 전체를 접두사로 포함한다면, 어떤 알파벳 순서를 사용해도 현재 순서를 만들 수 없으므로 빈 문자열 ""을 반환합니다.

4. 위상 정렬을 수행한다

그래프를 모두 구성한 뒤, 진입 차수가 0인 문자부터 큐에 넣고 위상 정렬을 수행합니다.

문자를 하나씩 큐에서 꺼내 정답에 추가하고, 해당 문자에서 나가는 간선을 제거합니다.

간선이 제거되면서 진입 차수가 0이 된 문자는 새롭게 큐에 추가합니다.

가능한 문자 순서가 여러 개라면 진입 차수가 0인 문자 중 어떤 것을 먼저 선택해도 됩니다.

5. 사이클을 확인한다

위상 정렬이 끝났는데 정답에 포함된 문자 수가 전체 고유 문자 수보다 작다면, 그래프에 사이클이 존재한다는 뜻입니다.

예를 들어 다음과 같은 관계가 만들어졌다면 올바른 문자 순서는 존재할 수 없습니다.

a → b
b → a

이 경우 빈 문자열 ""을 반환합니다.

그렇지 않다면 위상 정렬 결과를 문자열로 만들어 반환합니다.

복잡도

전체 단어에 포함된 문자 수의 합을 N, 고유 문자 수를 V, 문자 간 관계의 수를 E라고 하면 다음과 같습니다.

• 시간 복잡도: O(N + V + E)
• 공간 복잡도: O(V + E)