각각의 서로 다른 값이 서로 다른 작업 유형을 나타내는 tasks 리스트와 음수가 아닌 정수 k가 주어졌다고 가정해 보겠습니다. 각 작업을 완료하는 데는 1분이 걸리며, 같은 유형의 두 작업을 연속해서 수행하려면 그 사이에 반드시 k분을 기다려야 합니다. 어느 시점에서든 우리는 작업을 수행하거나 대기할 수 있습니다. 이때 모든 작업을 완료하는 데 필요한 최소 시간을 구하는 것이 문제입니다.
예를 들어 입력이 nums = [2, 2, 2, 3, 3, 2], k = 1이라면 출력은 7이 됩니다. 최적의 실행 순서는 [2, 3, 2, 3, 2, 대기, 2]이기 때문입니다.
문제 해결 접근 방식
이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 매 라운드마다 남아 있는 작업 중 가장 많은 빈도를 가진 작업부터 우선적으로 처리하면, 대기 시간을 최소화할 수 있습니다.
c:=nums에 있는 모든 값의 개수(빈도)를 저장합니다.ans:= 0,lastsize:= 0으로 초기화합니다.c가 비어 있지 않은 동안 다음을 반복합니다.lastsize:= 현재c에 남아 있는 서로 다른 작업 유형의 개수c에서 가장 빈도가 높은(k + 1)개의 값x에 대해:c[x]를 1 감소시킵니다.c[x]가 0이 되면 해당 항목을 제거합니다.
ans에(k + 1)을 더합니다.
- 최종적으로
ans + lastsize - (k + 1)을 반환합니다. 마지막 라운드에서는 불필요한 대기 시간이 포함되지 않도록 보정하는 것입니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, nums, k):
from collections import Counter
c = Counter(nums)
ans = 0
lastsize = 0
while c:
lastsize = len(c)
for x, _ in c.most_common(k + 1):
c[x] -= 1
if c[x] == 0:
del c[x]
ans += k + 1
return ans + lastsize - (k + 1)
ob1 = Solution()
nums = [2, 2, 2, 3, 3, 2]
k = 1
print(ob1.solve(nums, k))입력
[2, 2, 2, 3, 3, 2], 1
출력
7
코드 설명
Counter는 각 작업 유형별 빈도를 손쉽게 관리할 수 있게 해주는 파이썬의 유용한 도구입니다. most_common(k + 1) 메서드를 사용하면 한 라운드에서 처리 가능한 최대 (k + 1)개의 서로 다른 작업을 빈도순으로 선택할 수 있습니다. 이렇게 하면 같은 유형의 작업 사이에 최소 k분의 간격이 자연스럽게 확보됩니다.
전체 시간 복잡도는 작업 종류의 수와 총 작업 수에 따라 달라지지만, 일반적인 입력 크기에서 충분히 효율적으로 동작합니다. 마지막 반환문에서 lastsize - (k + 1)을 빼주는 이유는, 마지막 라운드에서는 남은 작업만 처리하고 추가 대기가 필요 없기 때문입니다.