[LeetCode] 621. Task Scheduler

621. Task Scheduler

Medium

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 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].

 

---

문제 풀이

문제 접근

1. Tasks 가 주어지고 한 시간에 하나의 일만 처리가능하다.
2. n 이 주어지는데, 같은 알파벳의 일은 반드시 n 시간의 idle 다음에 진행되어야한다.
3. 다른 알파벳 일이면 상관 없다.
4. 예를 들어 "A", "A", "B", "B" 가 주어지고 n 이 2 라면
5. A -> B -> idle -> A -> B 가된다. 
6. 이것의 길이를 구하자.

풀이

1. 제한을 보면 일들의 길이가 최대 10^4 이니, N^2 도 가능해 보인다. 
2. 이 문제는 그리디 문제로 특별한 풀이 법들이 존재한다. (구현 문제가 아니다 -_-)
3. idle 사이에 일이 들어가려면, 가장 많은 알파벳부터 찾아야하기 때문에 정렬을 사용한다. 
4. 알파벳의 갯수를 세서 정렬하고, 가장 큰 값을 구한다.
5. idle 의 최대 총 갯수를 구한다. 
6. idle 의 초기 시작 값은 최대 알파벳 개수 - 1 곱하기 idle 의 갯수이다. 
7. 정렬을 하더라도 최대 알파벳 갯수와 다음 알파벳 갯수가 같을 수 있기 때문에 idle time을 계산할때 예외를 처리해야한다.
8. 알파뱃 갯수를 계속 리스트에서 pop 하면서, 최대 알파벳 개수와 비교하여 가장 작은 것을 총 idle 갯수에서 뺀다.
9. idle 총 개수가 0 보다 클때까지 진행한다. 
10. 그리고 idle 총시간이 0 보다 클 경우 총 tasks 의 개수와 합쳐 반환, 반대로 tasks 의 총 개수만 반환한다.
11. idle 총 갯수에서 최대 알파벳 갯수 - 1 와 알파벳 개수 중 최소 값을 빼는 이유는 알파벳 갯수가 최대와 같을때가 존재할 수 있기 때문이다.
12. 위의 마이너스 계산을 하는 이유는 빈공간인 idle 에 다른 알파벳을 넣을 수 있어서 길이가 더 이상 늘어나지 않기 때문이다. 
13. 만약 알파벳들의 갯수를 모두 정리했지만 idle 갯수가 남아있다면 idle 갯수도 남겨야 하기 때문에 tasks 길이와 합쳐 반환한다. 
14. 반대로 idle 총 갯수가 0 보다 작을때 더 이상 계산을 하지 않는 이유는, 위에서 정렬을 했기 때문에 그 이후 처리해야할 알파벳의 갯수는 최대 알파벳 갯수와 같거나 작기 때문이다. 
15. n = 1 일때, 같다면 번갈아가면서 A -> B -> A -> B 진행하면 되기 때문이다. 만일 A, B, C가 2 개씩 n = 0 이거나 n = 1 이라면 이도 마찬가지로 A -> B -> C -> A -> B -> C 가 된다. 
16. 즉, tasks 갯수만 알면 답이 된다. 
17. 다시말하자면, 정렬 했기 때문에 알파벳의 갯수는 증가할 수 없고 idle 을 감소 시키면서 tasks 갯수와 더한 것이 답이 되는 이유는 idle 이라는 빈칸에 알파벳을 넣어 task 각각 갯수로 대체하기 때문이다 (빈칸에 못담으면 idle 은 길이에 합류). 

소스코드

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        ans = 0
        freq = Counter(tasks)
        freq = list(freq.values())
        freq.sort()
        max_freq = freq.pop()
        idle_time = (max_freq - 1) * n
        while freq and idle_time > 0:
            idle_time -= min(max_freq - 1, freq.pop())
        return idle_time + len(tasks) if idle_time > 0 else len(tasks)