[그리디] Leet code 621. Task Scheduler

리트코드 621번
같은 일을 n간격안에는 다시 하지 않는 최단 스케줄 시간을 구하라

풀이1 : 우선순위 큐+ Counter+ Greedy

• 우선순위 큐 : 남은 일의 길이와 일 키워드를 담은 튜플 (4,"A")
• Counter : 최초에 일의 횟수를 세기위해
• Queue : n번안에 다시 반복되지 않게 하기 위해 대기시키는 곳
• 그리디 아이디어 : 매번 가능한 일들중 가장 많은 시간이 남은 일부터 처리

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        pq = []  # 현재 가능한 일
        freqs = dict(collections.Counter(tasks))
        waitQ = collections.deque()  # 대기큐
        time = 0

        for freq in freqs:
            pq.append((-freqs[freq], freq))

        heapq.heapify(pq)  # 우선순위큐에 한번에 넣기
        
        while sum(freqs.values()) != 0:
            if waitQ:
                task = waitQ.popleft()

                if (task != "#"):
                    heapq.heappush(pq, (-freqs[task], task))

            if pq:  # 할일 있음
                task = heapq.heappop(pq)
                freqs[task[1]] -= 1
                
                if freqs[task[1]] != 0:  # 남은 일이라면 waitQ에 넣기
                    while len(waitQ) < n: # 앞에 최소 n개의 일이 있도록 
                        waitQ.append('#')
                    waitQ.append(task[1])
              
            else:  # 할일 없음
                waitQ.append('#')
              
            time += 1

        return time
        

테스트
["A","A","A","A","A","B","C","D","E","F","G"]
2

결과

deque([])
[(-5, 'A'), (-1, 'B'), (-1, 'C'), (-1, 'D'), (-1, 'E'), (-1, 'F'), (-1, 'G')]
A
=======================================
deque(['#', '#', 'A'])
[(-1, 'B'), (-1, 'D'), (-1, 'C'), (-1, 'G'), (-1, 'E'), (-1, 'F')]
B
=======================================
deque(['#', 'A'])
[(-1, 'C'), (-1, 'D'), (-1, 'F'), (-1, 'G'), (-1, 'E')]
C
=======================================
deque(['A'])
[(-4, 'A'), (-1, 'D'), (-1, 'F'), (-1, 'G'), (-1, 'E')]
A
=======================================
deque(['#', '#', 'A'])
[(-1, 'D'), (-1, 'E'), (-1, 'F'), (-1, 'G')]
D
=======================================
deque(['#', 'A'])
[(-1, 'E'), (-1, 'G'), (-1, 'F')]
E
=======================================
deque(['A'])
[(-3, 'A'), (-1, 'G'), (-1, 'F')]
A
=======================================
deque(['#', '#', 'A'])
[(-1, 'F'), (-1, 'G')]
F
=======================================
deque(['#', 'A'])
[(-1, 'G')]
G
=======================================
deque(['A'])
[(-2, 'A')]
A
=======================================
deque(['#', '#', 'A'])
[]
#
=======================================
deque(['#', 'A', '#'])
[]
#
=======================================
deque(['A', '#', '#'])
[(-1, 'A')]
A
=======================================
13