80. Task Scheduler

리트코드

• A에서 Z로 표현된 태스크가 있다. 각 간격마다 CPU는 한 번의 태스크만 실행할 수 있고, n번의 간격 내에는 동일한 태스크를 실행할 수 없다.

  더 이상 실행할 수 없는 경우 아이들(idle) 상태가 된다.

  모든 태스크를 실행하기 위한 최소 간격을 출력하라.

1. 우선순위 큐 이용

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counter = collections.Counter(tasks)
        result = 0
        
        while True:
            sub_count = 0
            
            #개수 순 추출
            for task, _ in counter.most_common(n+1):
                sub_count += 1
                result += 1
                
                counter.subtract(task)
                #0이하인 아이템을 목록에서 완전히 제거
                counter += collections.Counter()
            
            if not counter:
                break
                
            result += n - sub_count + 1
        
        return result
        

• 이 문제 또한 우선순위 큐를 이용해 그리디하게 풀 수 있는 문제다.

  • 그런데, 아이템을 추출한 이후에는 매번 아이템 개수를 업데이트해줘야 한다.

  • heapq만으로 구현하기에는 번거로운 작업이 필요하기에 Counter모듈을 사용해 코드를 구현해 본다.

• 전체 코드는 간단하지만, 여기에는 몇 가지 트릭이 있으며, 직관적으로 알아내기 어려운 부분들이 숨어 있다.

• 먼저, 우선순위 큐를 사용해 가장 개수가 많은 아이템부터 하나씩 추출해야 하는데, 문제는 전체를 추출하는 게 아니라 하나만 추출하고, 빠진 개수를 업데이트할 수 있는 구조가 필요하다는 점이다.

  • heapq를 사용하면 다음과 같은 형태가 된다.

    for task, count in collections.Counter(tasks).items():
    	heapq.heappush(heap, (-count, task)
       	...
           count, task = heapq.heappop(heap)
           ...
           heapq.heappush(heap, (-count + 1, task)
    

    • 각 태스크의 개수를 Counter로 계산하고 이 값을 힙에 추가한다.

    • heapq는 최소 힙(Min heap)만 지원하기 때문에 음수로 변환하여 저장한다.

    • heappop()은 항목 전체가 추출되기 때문에 꺼내서 활용한 이후에는

      heappush()로 개수로 줄여 (여기서는 음수이기에 +1을 하여) 다시 추가하는 작업이 필요하다.

  • 다음과 같은 일을 Counter만으로도 같은 일을 간결하게 처리할 수 있다.

    • most_common()은 가장 개수가 많은 아이템부터 출력하는 함수이며, 사실상 최대 힙과 같은 역할을 한다.

      • 그러나, pop()으로 추출되는 것이 아니기 때문에 subtract(task)를 지정해 1개씩 개수를 별도로 줄여나간다.

    • Counter 모듈은 개수를 줄이는 메소드도 지원하기 때문에 매우 편리하다.

      • 그런데, Counter는 0과 음수도 처리하는 특징이 있다.

      • 우리에게는 0이하는 필요가 없기 때문에, 매번 0 이하인지 체크하거나, 0일 때는 아예 삭제하는 기능이 필요하다.

        • 빈 collection.Counter()를 더하는 것인데, 이렇게 할 경우 0 이하인 아이템을 목록에서 아예 제거해버린다.

        • 매우 유용한 핵(Hack)이다.

• 또 다른 트릭은 n과 관련된 것이다.

  • 입력값을 most_common(n)으로 추출하고, 뒤에 idle을 덧붙이는 형태로 실행한다고 가정해보자.

    • 실행결과는 다음과 같다.

    A -> B -> idle -> A -> C -> idle -> A -> D

    • 결과는 8이다. 이건 정답이 아니다. 왜냐면 다음 순서대로 실행할 경우 7로, 한 번 더 줄일 수 있기 때문이다.

  • 이 경우 마지막에는 순서가 다르게 나와야 하는데, 앞 부분과 달리 마지막에만 순서가 다르게 나온게 하는 일은 별도의 예외 처리가 필요하다.

    • 이 같은 처리를 구현하는 일은 생각보다 쉽지 않다.

    • n이 아닌 n+1 만큼을 추출해보자. 즉 most_common(n + 1)을 추출하고 n+1개가 추출될 때는 idle 없이 실행한다.

    A -> B -> C -> A -> D -> idle -> A

    • 입력값이 n=2였기 때문에 n + 1을 추출했을 때 3개가 모두 나온다면 idle 없이 계속 진행한다.

    • 다음에는 A -> D 2개만 추출됐기 때문에 한 번 idle하고, 마지막으로 A를 출력한다.

  
  

• Counter 모듈을 무리하게 사용한 탓에 속도가 높은 편은 아니지만 문제없이 잘 풀린다.