[코테] 리트코드 그리디 알고리즘 621. Task Scheduler

621. Task Scheduler

문제 링크

https://leetcode.com/problems/task-scheduler/description/

문제 설명

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there’s a constraint: identical tasks must be separated by at least n intervals due to cooling time.

​Return the minimum number of intervals required to complete all tasks.

제한 사항

• 1 <= tasks.length <= 10^4
• tasks[i] is an uppercase English letter.
• 0 <= n <= 100

입출력 예 #1

1. Input : tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
2. Output : 8
3. Explanation : A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two cycles before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th cycle, you can do A again as 2 intervals have passed.

입출력 예 #2

1. Input : tasks = [“A”,”C”,”A”,”B”,”D”,”B”], n = 1
2. Output : 6
3. Explanation : A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

입출력 예 #3

1. Input : tasks = [“A”,”A”,”A”, “B”,”B”,”B”], n = 3
2. Output : 10
3. Explanation : A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

문제 풀이

Counter 모듈을 이용하여 문제를 풀이할 수 있다.

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counter = collections.Counter(tasks)
        result = 0

        while True:
            sub_count = 0
            # 개수 순 추출
            for task, _ in counter.most_common(n + 1):
                sub_count += 1
                result += 1

                counter.subtract(task)
                # 0 이하인 아이템을 목록에서 완전히 제거
                counter += collections.Counter()

            if not counter:
                break

            result += n - sub_count + 1

        return result