Python으로 동일한 유형의 작업 사이 k 시간 간격을 유지하며 모든 작업을 완료하는 데 필요한 최소 시간 구하기

문제 개요

정수 리스트 tasks가 주어지고, 각 항목은 서로 다른 작업 유형을 나타냅니다. 여기에 음수가 아닌 정수 k도 함께 주어집니다. 각 작업을 완료하는 데는 1단위의 시간이 걸리며, 작업은 반드시 주어진 순서대로 수행해야 합니다. 단, 같은 유형의 두 작업 사이에는 최소 k 단위의 시간 간격이 있어야 합니다. 어느 시점에서든 작업을 수행하거나 기다릴 수 있으며, 우리의 목표는 모든 작업을 완료하는 데 필요한 총 시간을 구하는 것입니다.

입력 예시와 결과 분석

예를 들어 입력이 tasks = [0, 1, 1, 2], k = 2라고 가정해 보겠습니다. 이 경우 출력은 6이 됩니다.

처음 두 작업(유형 0과 1)은 서로 다른 유형이므로 간격 없이 연속해서 실행할 수 있습니다. 그러나 시점 2에서 다음 작업은 직전에 실행한 작업과 같은 유형(1)이므로, 규칙에 따라 2타임 슬롯만큼 기다린 후에 작업을 수행해야 합니다. 마지막으로 다른 유형의 작업(유형 2)을 실행하면 됩니다. 결국 전체 진행 과정은 [0, 1, 대기, 대기, 1, 2]와 같으며, 총 6개의 타임 슬롯이 필요하다는 것을 알 수 있습니다.

접근 방법

이 문제는 각 작업 유형별로 다음 실행 가능 시각을 기록해 두고, 작업을 하나씩 처리하면서 필요한 대기 시간을 누적하는 방식으로 효율적으로 해결할 수 있습니다. 구체적인 절차는 다음과 같습니다.

tick := 0으로 초기화합니다.
slot := 각 작업 유형의 다음 실행 가능 시각을 저장할 새로운 맵(딕셔너리)을 생성합니다.
tasks의 각 작업 t에 대해 다음을 반복합니다.
- t가 slot에 존재하면 tf := slot[t]
- tf가 null이 아니고 tf - tick > 0이면, tick := tick + (tf - tick)으로 대기 시간을 더합니다.
- tick := tick + 1 (작업을 1단위 시간에 수행)
- slot[t] := tick + k (같은 유형 작업의 다음 실행 가능 시각 기록)
최종 tick 값을 반환합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 여기서 n은 작업의 개수입니다.

구현 예제

더 잘 이해하기 위해 다음 파이썬 구현 예제를 살펴보겠습니다.

def solve(tasks, k):
    tick = 0
    slot = {}
    for t in tasks:
        tf = slot.get(t)
        if tf is not None and tf - tick > 0:
            tick += tf - tick
        tick += 1
        slot[t] = tick + k

    return tick

tasks = [0, 1, 1, 2]
k = 2
print(solve(tasks, k))

입력

[0, 1, 1, 2]