Task Scheduler

Q: Task Scheduler의 시간 복잡도는 무엇인가요?

문자 수를 세는 데는 m 개의 작업에 대해 O(m) 이 걸리고, 그런 다음 수식은 26개의 개수를 읽으므로, 해법의 시간 복잡도는 O(m) 이고 추가 메모리 복잡도는 O(1) 입니다. 최대 힙 시뮬레이션은 작업마다 한 번씩 꺼내며, 문자 수가 k ≤ 26 일 때 O(m log k) 입니다.

Q: 작업 스케줄러에 유휴 시간이 필요하지 않은 경우는 언제인가요?

m ≥ (top-1) × (n+1) + atTop 일 때, 작업이 비어 있는 모든 슬롯을 채우고 간격을 남기는 대신 프레임을 늘리므로 답은 m 입니다. 예시 2의 "ABCABD" 와 n = 1 이 이에 해당합니다.

보통그리디 힙 해싱

+10

대문자로 이루어진 문자열 tasks와 정수 n이 주어집니다. 프로세서는 한 시간 단위마다 원하는 순서로 작업 하나를 실행하거나, 한 시간 단위 동안 유휴 상태로 있을 수 있습니다.

같은 문자를 두 번 실행하려면 그 사이에 최소 n개의 시간 단위가 필요합니다. 시간 단위 t에 실행된 문자는 가장 빨라도 시간 단위 t+n+1에 다시 실행할 수 있습니다. 모든 작업을 실행하는 데 필요한 최소 시간 단위 수를 반환하세요.

함수

leastInterval(tasks: string, n: integer) → integer

tasksstring: 과제마다 대문자 한 글자씩
ninteger: 같은 문자가 두 번 연속 나타날 때 그 사이에 있는 단위의 최소 개수
반환값integer: 유휴 상태인 단위를 포함한 최소 단위 수

제약 조건

1 ≤ tasks.length ≤ 10⁴
tasks에는 대문자 A부터 Z까지만 포함되어 있습니다.
0 ≤ n ≤ 100

예제

입력: tasks = "CACBAC"n = 2
출력: 7
설명: C는 두 유닛 간격으로 세 번 실행되므로, C의 실행만으로 총 7유닛이 걸립니다. C A B C A, 유휴, C 순서는 A와 B로 간격을 채우며 유휴 유닛 하나가 필요합니다: 7.

입력: tasks = "ABCABD"n = 1
출력: 6
설명: A와 B는 각각 두 번 실행되며, 실행 사이에는 1개의 단위가 있습니다. 순서 A B C A B D는 유휴 단위 없이 A와 B를 서로 떨어뜨려 놓으므로, 정답은 작업 수인 6입니다.

입력: tasks = "ZZZ"n = 3
출력: 9
설명: 실행할 Z만 있으므로 모든 간격은 유휴 상태입니다. Z, 유휴 시간 3단위, Z, 유휴 시간 3단위, Z입니다. 총 9단위입니다.

후속 질문

유휴 시간 단위마다 .가 들어가는 문자열로, 길이가 가장 짧은 스케줄도 하나 반환할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

순서는 직접 선택할 수 있으므로, 필요한 유휴 단위가 최소 몇 개인지가 관건입니다. 가장 자주 나오는 문자가 이를 결정합니다. 해당 문자의 실행은 n+1 단위 간격으로 배치해야 하며, 나머지 작업은 그 사이의 간격을 채웁니다. 최대 힙을 사용해 가장 자주 나오는 문자부터 실행하거나, 하나의 공식으로 간격을 직접 계산하세요.

최대 힙으로 라운드를 시뮬레이션하기

핵심 아이디어

시간을 n+1단위의 라운드로 나눕니다. 한 라운드에서 같은 문자를 두 번 실행할 수 없으며, 한 라운드의 어떤 슬롯에서 실행된 문자는 다음 라운드의 같은 슬롯에서 정확히 n+1단위 뒤에 다시 실행될 수 있습니다. 각 라운드에서는 남은 개수가 가장 많은 문자를 실행합니다. 이 문자들의 남은 실행은 서로 n+1만큼 떨어져 있어야 하므로, 라운드 끝에 유휴 시간이 생기게 할 수 있는 문자들입니다. 이 문자들을 먼저 실행하면 개수의 균형이 유지됩니다.

작업이 남아 있는 라운드는 n+1단위가 걸리며, 빈 슬롯은 유휴 시간입니다. 마지막 라운드에는 해당 라운드에서 실행한 작업만큼만 걸립니다. 예제 1에서는 C A B를 실행한 다음, C A와 유휴 시간 1단위를 실행하고, 마지막으로 C를 실행합니다. 3 + 3 + 1 = 7. 각 pop 연산은 작업 하나를 실행하므로, 작업이 m개이고 문자가 k ≤ 26개일 때 시간 복잡도는 O(m log k)입니다.

알고리즘

각 문자의 개수를 세고, 0보다 큰 개수를 최대 힙에 넣습니다.
힙이 비어 있지 않은 동안 한 라운드를 실행합니다. 최대 n+1개의 개수를 꺼내고, 1을 뺀 값이 여전히 0보다 큰 각 개수를 보관합니다.
보관한 개수들을 다시 넣습니다.
힙이 비어 있지 않으면 시간에 n+1을 더하고, 그렇지 않으면 해당 라운드에서 실행한 작업 수를 더합니다.
시간을 반환합니다.

import heapq
from collections import Counter


def leastInterval(tasks, n):
    # heapq is a min-heap, so store negated counts to pop the largest first.
    heap = [-c for c in Counter(tasks).values()]
    heapq.heapify(heap)
    time = 0
    while heap:
        # One round of n+1 slots: run the most frequent tasks left, each at most once.
        left = []
        ran = 0
        while ran < n + 1 and heap:
            c = -heapq.heappop(heap)
            ran += 1
            if c > 1:
                left.append(c - 1)
        for c in left:
            heapq.heappush(heap, -c)
        # A round lasts n+1 units, idle included; the last one ends with its last task.
        time += n + 1 if heap else ran
    return time

가장 자주 나오는 문자의 프레임 수 세기

핵심 아이디어

top을 가장 높은 개수라고 하고, 이 개수는 문자 X가 차지합니다. 마지막 실행을 제외하고 각 실행 뒤에 n개의 빈 슬롯이 있도록 X를 배치합니다. 즉, n+1 단위 길이의 프레임 top-1개를 배치한 다음 X의 마지막 실행을 둡니다. top개보다 적은 문자는 빈 슬롯에 들어갈 수 있으며, 프레임마다 하나씩 배치하면 각 문자의 복사본 사이 간격이 최소 n+1이 됩니다. top개인 다른 문자마다 끝에 단위 하나를 추가합니다. 가장 높은 개수를 가진 문자가 atTop개라면, 총 단위 수는 (top-1) × (n+1) + atTop입니다.

어떤 일정도 이보다 짧을 수는 없습니다. 처음 (top-1) × (n+1) 단위를 n+1개씩 top-1개의 구간으로 나눕니다. 각 최다 빈도 문자는 각 구간에서 최대 한 번만 실행되므로, 이 문자는 모두 구간이 끝난 뒤에도 실행할 횟수가 남습니다. 작업이 빈 슬롯보다 많다면 일부 프레임을 n+1보다 길게 만듭니다. 프레임이 길어지면 간격만 더 넓어지므로 유휴 시간이 발생하지 않으며, 답은 m입니다. 답은 두 값 중 더 큰 값입니다.

알고리즘

26개 문자를 각각 세세요.
가장 높은 개수인 top과 그 개수를 가진 문자의 수인 atTop을 찾으세요.
frames = (top-1) × (n+1) + atTop을 계산하세요.
frames와 작업 수 중 더 큰 값을 반환하세요.

def leastInterval(tasks, n):
    counts = [0] * 26
    for ch in tasks:
        counts[ord(ch) - ord("A")] += 1
    top = max(counts)
    at_top = counts.count(top)  # tasks that share the highest count
    # top-1 full frames of n+1 units, then one last slot per task at the top count.
    frames = (top - 1) * (n + 1) + at_top
    # With more tasks than frame slots, no idle unit is needed at all.
    return max(frames, len(tasks))

함정과 경계 사례

맨 위에서 동률인 글자들을 잊는 것. n = 5일 때 "MMNNPP"에서는 세 글자 모두 횟수가 2이므로, 답은 7이 아니라 (2-1) × 6 + 3 = 9입니다.
더 큰 값을 취하는 단계를 잊는 것. 예제 2에서 프레임은 (2-1) × 2 + 2 = 4를 산출하지만, 작업이 여섯 개라면 여섯 단위가 필요합니다.
마지막 라운드에 n+1단위를 전부 부과하는 것. 마지막 작업 뒤에는 기다릴 일이 없으므로, 예제 3의 결과는 9가 아니라 12가 됩니다.
라운드 안에서 횟수를 다시 넣는 것. 그러면 같은 글자를 해당 라운드에서 다시 꺼내게 되어, 너무 가까운 간격으로 두 번 실행될 수 있습니다.

자주 묻는 질문3

Task Scheduler의 시간 복잡도는 무엇인가요?

문자 수를 세는 데는 m개의 작업에 대해 O(m)이 걸리고, 그런 다음 수식은 26개의 개수를 읽으므로, 해법의 시간 복잡도는 O(m)이고 추가 메모리 복잡도는 O(1)입니다. 최대 힙 시뮬레이션은 작업마다 한 번씩 꺼내며, 문자 수가 k ≤ 26일 때 O(m log k)입니다.

작업 스케줄러에 유휴 시간이 필요하지 않은 경우는 언제인가요?

m ≥ (top-1) × (n+1) + atTop일 때, 작업이 비어 있는 모든 슬롯을 채우고 간격을 남기는 대신 프레임을 늘리므로 답은 m입니다. 예시 2의 "ABCABD"와 n = 1이 이에 해당합니다.

입력 문자열의 순서가 중요한가요?

아니요. 프로세서가 작업을 실행하는 순서는 직접 선택할 수 있으므로 각 문자가 몇 번 나타나는지만 중요합니다. "CACBAC"과 "CCCAAB"은 n = 2일 때 둘 다 7개의 단위가 필요합니다.

def leastInterval(tasks, n):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

tasks = "CACBAC"
n = 2

예상 출력