Task Scheduler | LeetCode 826 | Python3 🐍

 

📄 목차

 

 

🤔 문제 : Task Scheduler | LeetCode 826

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/114/others/826/

input으로 Task리스트와 cooltime값인 숫자 n이 들어옵니다. 

같은 Task사이에는 무조건 n 이상의 cooltime을 쉬어야 합니다. 

이런 상황에서 주어진 task를 다 처리하기 위해 필요한 최소 cpu time을 구하는 문제입니다.

 

가장 남은 task를 가장 먼저 처리한다 까지는 직관적으로 이해가 되었고,

그래서 task를 처리해가며 남은 task를 계속 sorting해서 다음 task를 뽑고, cooltime은 deque로 관리하였는데도 TLE가 나오더라구요.. ㅠㅠ 

 

여러 삽질과.. TLE를 전전하다(ㅜㅜ) 결국 discussion을 보았는데요,

크게 2종류의 풀이가 있었습니다.

1. 가장 긴 task를 먼저 처리해가며 greedy로 풀 경우 heap 을 활용해야 한다(!!)

2. 가장 긴 task의 갯수를 활용하여 수학적으로 푼다 

 

 

💡 풀이

1. heap + greedy 활용

같은 task만 여러번 남으면 중간에 계속 cooltime을 넣어줘야 하므로 cpu time이 늘어날 수 밖에 없습니다.

ex) ["A", "A", "B", "B"], n=1일 때

A -> B -> A -> B로 처리할 경우 cputime = 4

A -> A -> B -> B로 처리할 경우 A -> idle -> A -> B -> idle -> B 가 되어야 하므로 cputime = 6

 

따라서, 가장 많이 남은 task들 위주로 골고루 섞어가며 처리해야 합니다. 

 

1. heap 을 활용해 가장 많이 남은 task를 뽑습니다.

2. task처리 후 deque에 넣어 n시간 동안은 heap에 들어가지 않도록 합니다.

3. n시간이 지난 task는 남은수행 -1을 하여 다시 heap에 넣습니다.

from collections import Counter
import heapq
from typing import List
from collections import deque
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # deq : 쿨타임동안 task를 보관 
        deq = deque()
        # heap : 가장 많이 남은 task가 먼저 나오도록 task들을 heap에 정렬하여 보관 
        heap = []

        for f in list(Counter(tasks).values()): heapq.heappush(heap, -f)

        cpu = 0
        while heap or deq:
            cpu = cpu+1
            task = None
            # heap에서 task 하나 꺼냄 
            if heap: task = heapq.heappop(heap)
            # task < -1인 경우(아직 더 처리할게 있는 경우), deq에 n만큼 넣어둠 
            if task and task < -1: deq.appendleft((cpu+n, task))
            # deq에 task가 n만큼 보관되었으면, 다시 꺼내서 heap에 넣어줌 
            if deq and deq[-1][0] == cpu:
                resume = deq.pop()
                if resume[1] is not None: heapq.heappush(heap, resume[1]+1)
            # print(cpu, task, heap, deq)
        return cpu

 

 

아래는 heap 없이 풀려고 했던... 슬픈 기록입니다,,

답은 나오긴 하는데.. 코드는 무진장 길고 무슨 코드인지 잘 이해도 안가며 속도도 느리죠.. ㅠㅠ

from typing import List
from collections import deque

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        tasksMap = {} # "A" : 2, "B" : 3
        tasksCount = []
        for i in range(10**4+1):
            tasksCount.append([])
        count = []
        unavailableTask = {}
        deq = deque()
        for t in tasks:
            if t in tasksMap: tasksMap[t] += 1
            else: tasksMap[t] = 1
        for t in tasksMap:
            if tasksCount[tasksMap[t]]:
                tasksCount[tasksMap[t]].append(t)
            else:
                tasksCount[tasksMap[t]] = [t]
                count.append(tasksMap[t])

        count.sort(reverse = True)
        # print(tasksCount)

        cpuTime = 0
        while 1:
            if not count: break
            # print(unavailableTask)
            # print(count)
            currTask = None
            temp = None
            for c in count:
                if currTask: break
                for i in range(len(tasksCount[c])):
                    t = tasksCount[c][i]
                    if t not in unavailableTask or unavailableTask[t] is False:
                        currTask = t
                        temp = c
                        break

            if currTask:
                unavailableTask[currTask] = True
                tasksCount[temp].remove(currTask)
                if len(tasksCount[temp]) == 0:
                    count.remove(temp)
                if temp > 1:
                    tasksCount[temp-1].append(currTask)
                    if len(tasksCount[temp-1]) == 1:
                        count.append(temp-1)
                        count.sort(reverse = True)
            deq.appendleft(currTask)
            if len(deq) == n+1: unavailableTask[deq.pop()] = False
            cpuTime += 1
            # print(currTask)
            # if cpuTime > 10: break
        return cpuTime

 

참고) heap과 list의 수행시간 비교

list를 정렬하여 최댓값을 구하면 정렬하는데 시간 O(NlogN)이 사용됩니다.

하지만 heap은 트리 구조로 최댓값을 구하는데 O(logN)만 소요되어 훨씬 빠릅니다.

최댓값이나 최솟값을 계속 활용해야 하는 문제라면 heap 자료구조를 떠올릴 수 있어야 합니다. 

참고. https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

 

 

 

2. idle 상황을 파악하여 더 간단하게 해결

이 문제는 idle이 한번이라도 나타나는 경우와 idle없이 처리가 가능한 경우로 나뉘어집니다.

 

분류	tasks	n	처리순서	cpuTime
idle없이 처리 가능	[A, A, B, B]	0	A -> A -> B -> B	4 ( = len(tasks))
idle없이 처리 가능	[A, A, B, B]	1	A -> B -> A -> B	4 ( = len(tasks))
idle없이 처리 가능	[A, A, B, C]	1	A-> B -> A -> C	4 ( = len(tasks))
idle 필요	[A, A, B, B]	2	A-> B -> idle -> A -> B	5
idle없이 처리 가능	[A, A, B, C]	2	A-> B -> C -> A	4 ( = len(tasks))
idle 필요	[A, A, B]	2	A -> B -> idle -> A	4
idle 필요	[A, A, A, B]	2	A -> B -> idle -> A -> idle -> idle -> A	6

 

idle없는 경우의 cpuTime은 len(tasks)입니다.

idle이 필요한 경우의 cpuTime은 가장 많이 나온 task가 몇 번 나왔느냐에 따라 좌우됩니다. 

 

1) A가 총 3번으로 가장 많이 나왔고 n이 3이라면

A _ _ _A _ _ _ A              [9 = (3+1) * (3-1) + 1]

순서로 처리해야 합니다. 

이 때 _에 idle이 들어가던 다른 task가 들어가던 상관 없습니다. 

 

2) 만약 A, B가 총 3번으로 똑같이 많이 나왔다면

A B _ _ A B _ _ A B       [9 = (3+1) * (3-1) + 2]

순서로 처리해야 합니다. 

1)의 풀이에서 _자리에 B만 들어갔고, 제일 마지막에 B가 하나 더 들어가는것만 다릅니다. 

A, B외의 task가 4개보다 많다면 idle없이 처리 가능한 케이스가 될 것입니다.

 

3) 만약 A, B, C가 총 3번으로 똑같이 많이 나왔다면

A B C _ A B C _ A B C [9 = (3+1) * (3-1) + 3]

순서로 처리해야 합니다. 

1)의 풀이에서 _자리에 B, C만 들어갔고, 제일 마지막에 B, C가 하나씩 더 들어가는것만 다릅니다. 

A, B, C외의 task가 2개보다 많다면 idle없이 처리 가능한 케이스가 될 것입니다.

 

즉, tasks 중에 가장 중복해서 많이 나온 task의 나온 횟수를 maxValue라 할 때,

maxValue만큼 나온 task의 수를 maxCount라고 하면

idle이 하나라도 존재할 때 cpuTime은 (n+1) * (maxValue-1) + maxCount가 됩니다. 

from collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        frequency = list(Counter(tasks).values())
        maxValue = max(frequency)
        maxCount = frequency.count(maxValue)
        return max(len(tasks), (n+1)*(maxValue-1)+maxCount)