[Counting 문제] LEETCODE.621 Task Scheduler

문제풀이

해당 문제에서의 중요한 Factor는 2가지이다.

가장 큰 빈도의 Task의 종류는 무엇인가? 가장 빈번한 Task의 작업수는 몇개인가?

이 두 가지 Factor를 기반으로 생각해보자. n만큼의 idle을 주고 동일 문자가 반복 사용이 가능하다는 제약 하에 우리가 해결하고자 하는 것은 최소한의 길이로 작업을 완료해야 한다는 점이다.
1. 가장 빈도가 큰 작업들을 추출한 후 Idle 개수를 산출한다.
2. 전체 작업 중 가장 빈도가 큰 작업들의 수를 차감한 수량을 잔여 작업으로 판단 한다.
3. 1에서 구한 Idle 값과 2에서 구한 잔여 작업을 비교하여 Idle 내 잔여 작업을 모두 끼워넣을 수 있는 지 확인한다. Idle 값이 더 크면 Idle 내 모두 잔여 작업을 끼워넣을 수 있고 아닌 경우라면 필요한 공간은 잔여작업 수량이 된다.
4.전체 결과값은 3에서 구한 값과 빈도가 큰 작업들의 작업수를 더한 값이 최종 정답이 된다.

from collections import Counter
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        task_list = Counter(tasks).values()
        max_task_cnt = max(task_list)
        num_distinctmax_cnt = sum(1 for i in task_list if i==max_task_cnt)
        idle = (n-num_distinctmax_cnt+1)*(max_task_cnt-1)
        remain_task= sum(task_list)-max_task_cnt*num_distinctmax_cnt        
        if idle>remain_task:
            return idle+max_task_cnt*num_distinctmax_cnt
        else:
            return  remain_task+max_task_cnt*num_distinctmax_cnt            

![](https://velog.velcdn.com/images/relighting123/post/13b3bf85-d800-4ac1-b7d1-4e3809629e6d/image.png)


       

## Lookback
1. 이 문제는 리트코드 1953 Number of Weeks to Complete Tasks 과 사실 동일한 문제로 보인다. 차이점이라고 한다면 n=1이라는 점과 중간에 idle이 발생하게 되면 그 전까지의 값을 결과값으로 산출해야 한다는 1953 문제의 차이점이 있다. 
2. 해당 코드는 알고리즘보다는 어느정도 수학적인 부분과 연관이 된다고 느껴진다 1953 문제를 풀지 않았다면 이 문제를 위와 같은 방식으로 접근할 수 있었을까 싶다.