링크 : https://leetcode.com/problems/task-scheduler/submissions/

description

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

example

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Constraints

• 1 <= task.length <= 104
• tasks[i] is upper-case English letter.
• The integer n is in the range [0, 100]

풀이

코드

from collections import Counter
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        if n == 0 : return len(tasks)
        
        taskDict = dict(Counter(tasks))
        maxNum = 0
        maxCnt = 0
        
        for task, value in taskDict.items() :
            if value > maxNum :
                maxNum = value
                maxCnt = 1
            elif value == maxNum : maxCnt += 1
        
        if len(taskDict) <= n+1 : return (maxNum-1) * (n+1) + maxCnt
        else: return max((maxNum-1) * (n+1) + maxCnt, len(tasks))

결과

Runtime: 384 ms, faster than 84.19% of Python3 online submissions for Task Scheduler.
Memory Usage: 15 MB, less than 18.86% of Python3 online submissions for Task Scheduler.

설명

알고리즘 책에서 본 Counter를 사용해봤다! 풀다가 디스커션을 참고한 것은 비밀….

먼저 Counter로 각 task가 몇 개씩 있는지 센 후에 딕셔너리로 변환한다. for 문에서 items 메소드를 이용해 각 키, 값을 꺼내오면서 순회한다. task 개수가 가장 큰 것(maxNum)과 큰 값을 가지는 task의 개수(maxCnt)를 구한다.

만약 키의 개수가 n+1보다 작다면, 큰 애를 n만큼 띄엄띄엄 떨어뜨려 놓은 모양을 생각하며 idle을 채워놓은 모양에서 같은 개수를 가지는 애를 더해준다! 큰 경우에는 위에서 구한 값과 전체 태스크 개수와 비교해서 더 큰 값을 넣어준다. 왜냐하면 n이 작으면 채워넣을 곳이 부족해지기 때문이다!!!