[1스4코2파] # 237. LeetCode 621. Task Scheduler

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (237차)
[4코1파] 2023.01.13~ (229일차)
[1스4코1파] 2023.04.12~ (140일차)
[1스4코2파] 2023.05.03 ~ (118일차)

Today :

2023.08.28 [237일차]
621. Task Scheduler
https://leetcode.com/problems/task-scheduler/

621. Task Scheduler

문제 설명

CPU가 수행해야 하는 task를 나타내는 문자 배열이 주어지고, 각 task 는 순서에 관계없이 완료될 수는 있으나, 주어지는 n은 'cooldown'을 나타내고, 같은 알파벳은이 cooldown이 지나기 전까지 실행이 불가능하다.
각 task는 하나의 시간 단위로 완료되고, cpu가 모든 작업을 완료하는데 걸리는 최소 단위 수를 return 하기

문제 풀이 방법

배열에 있는 task 중에서 가장 많은 task를 기준으로 작업이 결정되므로 count를 사용해서 각 task가 몇개 있는지에 대한 count 배열을 만들고 그 개수에 따라 MaxHeap을 구현한다.
그 이후에 maxHeap을 꺼내오면서 queue 를 하나 더 구현해서, 시간과 tak에 대해서 넣어주면 되는데 이해 잘 안됨

내 코드

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        maxHeap = [-cnt for cnt in count.values()]
        heapq.heapify(maxHeap)

        time = 0
        q = deque()
        
        while maxHeap or q:
            time += 1
            if maxHeap:
                cnt = 1 + heapq.heappop(maxHeap)
                if cnt:
                    q.append([cnt, time+n])
            if q and q[0][1] == time:
                heapq.heappush(maxHeap, q.popleft()[0])
            
        return time

증빙

여담

이거 무슨말이냐