A
에서 Z
로 표현된 태스크가 있다. 각 간격마다 CPU는 한 번의 태스크만 실행할 수 있고, n
번의 간격 내에는 동일한 태스크를 실행할 수 없다.
더 이상 실행할 수 없는 경우 아이들(idle) 상태가 된다.
모든 태스크를 실행하기 위한 최소 간격을 출력하라.
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
이 경우 마지막에는 순서가 다르게 나와야 하는데, 앞 부분과 달리 마지막에만 순서가 다르게 나온게 하는 일은 별도의 예외 처리가 필요하다.
이 같은 처리를 구현하는 일은 생각보다 쉽지 않다.
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
모듈을 무리하게 사용한 탓에 속도가 높은 편은 아니지만 문제없이 잘 풀린다.