책 풀이
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꽤 어려웠던 문제다. 핵심은 많이 남은 순대로 n에 맞게 뽑는 것을 반복하면된다.
most_common은 가장 개수가 많은 아이템부터 출력하는 함수이다. 사실상 최대힙과 같은 역할을 하고, subtract(task)를 통해서 1개씩 개수를 줄여나간다.
Counter 모듈은 0과 음수도 처리한다.
counter.subtract(task) counter += collections.Counter()빈 collection.Counter()를 더하면, 0이하인 아이템을 목록에서 아예 제거해버린다.
만약 most_common(n) 다음 idle을 덧붙인다 생각해보자.
tasks = ["A", "A", "A", "B", "C", "D"], n = 2
이 경우 입력값의 결과는 A -> B -> idle -> A -> C -> idle -> A -> D이다. 하지만 최소화하려면 A-> B -> C -> A -> D -> idle -> A가 최선이다. n이 아닌 n + 1만큼을 추출하고, 즉 most_common(n+1), n+1개가 추출되면 idle없이 실행하면된다.
