Leetcode 621. Task Scheduler - Python

Leetcode 621 문제 보기

 

문제 이해하기

CPU가 순차적으로 task를 하나씩 처리한다. Task는 영문 알파벳 대문자로 표시된다.

이때 같은 종류의 task는 연달아 진행할 수 없고, 휴식(idle)이 필요하다.

또한 동일한 종류의 task 사이에는 n만큼의 idle이 필요하다.

clock이 일정하게 흐르고 각 task 및 idle은 종류에 상관없이 1clock의 시간을 소모한다.

모든 task를 마무리할 수 있는 가장 빠른 시간을 구하여라.

 

아이디어 구상

Leetcode Medium 난이도 문제였지만, 개인적으로 웬만한 Hard 난이도보다 어려운 문제였다.

 

이 문제에서 키 포인트는 다음과 같다.

"가장 많이 수행해야하는 task부터 처리하는 것이 유리하다."

이를 위해 최대힙을 사용하여 문제를 풀었다.

 

때문에 우선 A부터 Z까지의 task가 각각 몇 개 있는지 센다.

이후 반복문을 통해 한 clock이 진행될 때마다 수행해야하는 task의 남은 횟수를 줄여나간다. Task는 최대힙에 넣어 task 수행 시 가장 많이 수행해야하는 task부터 줄여나간다.

이때 한 번 수행된 task는 n번의 idle 이후에 재수행될 수 있음을 코드로 처리하기 위해, n번의 clock이 지난 후에 다시 수행될 수 있도록 queue에 대기시킨다.

clock이 진행되며 해당 시간이 되면 queue에 대기 중인 task를 다시 heap에 넣고 위 과정을 반복한다.

 

이러한 아이디어는 웹브라우저상 Javascript 엔진의 Event loop 및 Callback queue가 수행되는 원리에서 차용했다.

 

 

풀이

수행해야 할 Task의 횟수를 세고, 이를 최대힙으로 heapify한다.

types_of_tasks = collections.Counter(tasks)
heap = [-item for item in types_of_tasks.values()]
heapq.heapify(heap)

 

Task queue를 선언한다. 최적화를 위해 deque를 사용했다.

queue = collections.deque()

 

하나의 clock 시간을 snapshot이라 표현했다.

snapshot = 0

 

이제 clock이 진행되면서 최대힙에서 task를 하나씩 pop하여 수행할 것이다.

pop한 task에서 남은 수행 횟수를 1 차감하고,

1. idle 이후 다시 수행가능한 시각과 2. 남은 수행 횟수를 함께 tuple로 묶어 queue에 넣어 주자.

이후 queue에 대기하고 있는 task의 다시 수행가능한 시각과 snapshot, 즉 현재 시각이 맞아떨어지면 queue에서 해당 task를 꺼내 다시 최대힙에 넣어준다.

이 과정을 반복해 만약 heap과 queue가 모두 비게 되면, 모든 task를 수행했다는 뜻이므로 반복을 종료한다.

while heap or queue:
    snapshot += 1
    if heap:
        remaining_task = heapq.heappop(heap) + 1
        if remaining_task:
            queue.append((snapshot + n, remaining_task))
                
    if queue and queue[0][0] == snapshot:
        heapq.heappush(heap, queue.popleft()[1])

 

전체 코드는 다음과 같다.

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        types_of_tasks = collections.Counter(tasks)
        heap = [-item for item in types_of_tasks.values()]
        heapq.heapify(heap)
        queue = collections.deque()
        
        snapshot = 0
        while heap or queue:
            snapshot += 1
            if heap:
                remaining_task = heapq.heappop(heap) + 1
                if remaining_task:
                    # complete one task and this task can be done again after snapshot + n
                    queue.append((snapshot + n, remaining_task))
                
            if queue and queue[0][0] == snapshot:
                heapq.heappush(heap, queue.popleft()[1])
        
        return snapshot

---

 

Leetcode 621. Task Scheduler

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

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다