Alien Dictionary

+10

단어 목록이 당신이 모르는 알파벳 순서로 정렬되어 있습니다. 26개의 영어 소문자가 어떤 비밀 순서로 배열되어 있습니다. 단어는 일반적인 방식으로 비교합니다. 두 단어가 다른 첫 번째 위치에서 순서가 결정되며, 한 단어가 다른 단어의 시작 부분과 같으면 더 짧은 단어가 먼저 옵니다.

단어에 나타나는 문자들을 알파벳 순서대로 하나의 문자열로 반환하세요. 여러 순서가 가능하면 일반적인 사전 순서에서 가장 먼저 오는 것을 반환하세요. 가능한 순서가 없으면 "invalid"를 반환하세요.

함수

alienOrder(words: string-array) → string

wordsstring-array: 알 수 없는 알파벳 순으로 정렬된 단어
반환값string: 조건에 맞는 가장 작은 순서의 문자들 또는 "invalid"

제약 조건

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
모든 단어는 소문자 영어 문자만 포함합니다.
같은 단어가 두 번 이상 나타날 수 있습니다.

예제

입력: words = ["tea", "ten", "ate", "act", "cat"]
출력: "etacn"
설명: tea가 ten보다 앞에 오므로 a가 n보다 앞에 옵니다. 다른 쌍에서는 t가 a보다 앞에 오고, t가 c보다 앞에 오며, a가 c보다 앞에 옵니다. e에 대한 규칙은 없으므로 가장 작은 순서는 e로 시작합니다: e, t, a, c, n.

입력: words = ["bat", "tab", "tub", "bus"]
출력: "invalid"
설명: bat을 tab보다 앞에 놓으면 b가 t보다 앞에 오고, tub을 bus보다 앞에 놓으면 t가 b보다 앞에 옵니다. 두 조건을 모두 만족할 수 없으므로 어떤 순서도 맞지 않습니다.

입력: words = ["cooking", "cook"]
출력: "invalid"
설명: cook는 cooking의 시작 부분이므로, 어떤 알파벳에서도 먼저 옵니다. 그런데 목록에서는 두 번째에 놓여 있어, 알파벳 순서로는 설명할 수 없습니다.

후속 질문

피팅 순서가 유일한지 어떻게 알 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

서로 이웃한 각 단어 쌍은 처음으로 다른 위치에서 최대 하나의 규칙을 만듭니다. 즉, 문자 x가 문자 y보다 앞에 옵니다. 조건에 맞는 순서는 이러한 규칙의 위상 정렬입니다. 순환이 있거나 단어가 자신의 접두어보다 앞에 오면 목록을 만들 수 없습니다. 준비된 문자 중 가장 작은 문자를 항상 배치하는 최소 힙은 가장 작은 순서를 제공합니다.

문자의 모든 순서를 시도해 보세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

서로 다른 k개의 문자를 배열하는 한 가지 방법을 시험하려면 이웃한 각 쌍을 확인하면 됩니다. 처음으로 다른 위치에서 첫 번째 단어의 문자가 더 앞에 와야 합니다. 차이가 없다면 첫 번째 단어가 더 길어서는 안 됩니다. 알파벳순 배열에서 시작해 다음 순열로 배열을 오름차순으로 살펴보고, 조건을 처음 만족하는 배열이 조건에 맞는 가장 작은 순서입니다.

k개의 문자는 k!가지로 배열할 수 있습니다. 10개면 3,628,800가지이고 26개면 약 4 × 10^26가지이며, 각 검사에서 최대 5 × 10^4개의 문자를 읽습니다. 조건에 맞는 배열이 없으면 모든 배열을 시도합니다.

알고리즘

서로 다른 문자들을 모아 알파벳순으로 정렬합니다.
현재 배열에서 각 문자의 순위를 기록합니다.
이웃한 각 쌍을 확인합니다. 처음으로 다른 위치에서 첫 번째 단어의 문자는 더 낮은 순위여야 합니다. 차이가 없다면 첫 번째 단어가 더 길어서는 안 됩니다.
모든 쌍이 통과하면 배열을 반환하고, 그렇지 않으면 다음으로 더 큰 배열로 이동합니다.
다음 배열이 없으면 "invalid"를 반환합니다.

from itertools import permutations


def fits(words, rank):
    # The list is sorted under rank when every neighbouring pair is in order.
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                if rank[x] > rank[y]:
                    return False
                break
        else:
            # One word starts the other: the shorter must come first.
            if len(first) > len(second):
                return False
    return True


def alienOrder(words):
    letters = sorted(set("".join(words)))
    # permutations() of a sorted list yields the orders from smallest to largest,
    # so the first order that fits is the answer.
    for order in permutations(letters):
        rank = {ch: i for i, ch in enumerate(order)}
        if fits(words, rank):
            return "".join(order)
    return "invalid"

최소 힙을 사용한 Kahn 알고리즘

핵심 아이디어

이웃한 단어 쌍에서는 첫 번째로 다른 문자만 중요합니다. act가 cat보다 앞에 있다는 것은 a가 c보다 앞선다는 뜻이며, 그 뒤의 문자는 비교하지 않습니다. 따라서 각 쌍은 최대 하나의 간선만 만듭니다.

Kahn 알고리즘은 간선을 순서로 바꿉니다. 각 문자의 진입 간선 수를 세고, 그 수가 0인 문자를 배치한 다음, 그 문자의 나가는 간선을 제거하고 반복합니다. 사이클에 있는 문자는 사이클에서 바로 앞에 있는 문자로부터 오는 간선이 항상 남아 있으므로 배치되지 않습니다. 등장한 문자보다 배치된 문자가 적으면 답은 "invalid"입니다.

배치할 수 있는 문자들을 최소 힙에 넣고 가장 작은 문자를 배치합니다. 가능한 모든 순서는 배치 가능한 문자로 시작하므로, 이렇게 하면 가능한 가장 작은 첫 문자를 고를 수 있습니다. 또 문자를 배치하면 간선만 제거하므로 다른 문자의 배치를 막지 않습니다. 첫 번째 예시에서는 처음에 e와 t를 배치할 수 있고, e가 먼저 배치됩니다. 일반 큐를 사용해도 올바른 순서를 얻을 수 있지만, 항상 가장 작은 순서가 되지는 않습니다.

알고리즘

단어에 나타나는 모든 문자를 표시합니다.
각 이웃한 단어 쌍에서 처음으로 다른 위치를 찾아 두 문자 사이에 간선을 한 번 추가합니다. 다른 부분이 없고 첫 번째 단어가 더 길면 "invalid"를 반환합니다.
들어오는 간선의 수를 세고, 진입 차수가 0인 표시된 모든 문자를 최소 힙에 넣습니다.
가장 작은 문자를 꺼내 뒤에 붙입니다. 해당 문자가 가리키는 각 문자의 진입 차수를 낮추고, 0이 된 문자는 힙에 넣습니다.
표시된 문자를 모두 배치했다면 배치된 문자를 반환하고, 그렇지 않으면 "invalid"를 반환합니다.

import heapq


def alienOrder(words):
    # Letters are numbered 0 for 'a' up to 25 for 'z'.
    present = [False] * 26
    for word in words:
        for ch in word:
            present[ord(ch) - 97] = True
    # before[a][b] is True once you know letter a comes before letter b.
    before = [[False] * 26 for _ in range(26)]
    indegree = [0] * 26
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                # Only the first difference tells you anything.
                a, b = ord(x) - 97, ord(y) - 97
                if not before[a][b]:
                    before[a][b] = True
                    indegree[b] += 1
                break
        else:
            # No difference: one word starts the other, so the shorter must come first.
            if len(first) > len(second):
                return "invalid"
    # A min-heap of the letters with nothing left before them.
    heap = [c for c in range(26) if present[c] and indegree[c] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        c = heapq.heappop(heap)
        order.append(chr(c + 97))
        for nxt in range(26):
            if before[c][nxt]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    heapq.heappush(heap, nxt)
    # A letter on a cycle never gets down to indegree 0, so it is never placed.
    if len(order) < sum(present):
        return "invalid"
    return "".join(order)

함정과 경계 사례

한 쌍에서 규칙을 두 개 이상 가져옵니다. act와 cat의 두 번째 위치를 읽으면 a 앞에 c가 추가되어 첫 번째 예시가 잘못된 사이클이 됩니다.
접두사 함정을 놓칩니다. cooking이 cook보다 앞에 있고 서로 다른 문자가 없으므로, 차이만 처리하는 루프는 순서를 반환합니다.
어떤 규칙에도 등장하지 않는 문자를 누락합니다. 첫 번째 예시에서는 어떤 규칙에도 e가 언급되지 않지만, 답에는 포함되어야 합니다.
반복된 규칙을 진입 차수에서는 두 번 세고 저장은 한 번만 합니다. 해당 문자의 진입 차수가 0이 되지 않아 유효한 목록을 사이클로 보고합니다.
서로 같은 두 이웃 단어를 접두사 함정으로 취급합니다. 반복된 단어는 순서가 맞습니다.

자주 묻는 질문3

Alien Dictionary의 시간 복잡도는 얼마인가요?

O(C + k²)이며, 여기서 C는 전체 문자 수이고 k ≤ 26은 서로 다른 문자의 수입니다. 목록을 한 번 순회하면 모든 첫 번째 차이를 찾을 수 있으며, Kahn 알고리즘은 최대 k²개의 간선을 방문합니다. 간선 테이블은 O(k²)의 공간을 차지합니다.

왜 인접한 단어만 비교할까요?

정렬 상태는 추이적입니다. 모든 단어가 다음 단어보다 작거나 같으면 전체 목록이 정렬된 것입니다. 따라서 서로 멀리 떨어진 두 단어에서 읽을 수 있는 규칙은 그 사이에 있는 인접한 쌍들로부터 이미 따라옵니다.

단어가 자기 자신의 접두사 앞에 오면 왜 유효하지 않을까요?

모든 알파벳에서 단어는 그 자체의 접두사 뒤에 옵니다. 비교할 때 더 짧은 단어에서 차이를 찾기 전에 글자가 먼저 바닥나기 때문입니다. 이는 규칙 사이에 순환이 없어도 목록을 만들 수 없는 유일한 경우입니다.

def alienOrder(words):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

words = ["tea", "ten", "ate", "act", "cat"]

예상 출력

"etacn"