각각 다른 값이 다른 작업 유형을 나타내고 음이 아닌 정수 k가 있는 작업이라는 값 목록이 있다고 가정합니다. 각 작업은 완료하는 데 1분을 원하지만 동일한 유형의 두 작업을 수행하는 사이에 k분을 기다려야 합니다. 언제든지 작업을 수행하거나 기다릴 수 있습니다. 모든 작업을 완료하는 데 걸리는 최소 시간을 찾아야 합니다.
따라서 입력이 nums =[2, 2, 2, 3, 3, 2], k =1과 같으면 최적의 순서는 [2, 3, 2, 3, 2, 대기 중, 2].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
c :=숫자로 된 모든 값의 개수
-
답변 :=0, 마지막 크기 :=0
-
c가 0이 아닌 동안 do
-
lastsize :=c의 크기
-
c의 가장 일반적인 (k + 1) 값의 각 값 x에 대해 수행
-
c[x] :=c[x] − 1
-
c[x]가 0과 같으면
-
c[x]
제거
-
-
-
-
ans :=ans + k + 1
-
-
return as + 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