leetcode 621. Task Scheduler 과업 스케줄러 문제풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

https://leetcode.com/problems/task-scheduler/

Task Scheduler - LeetCode

입력: 과제의 종류를 알파벳으로 표현한 리스트와 같은 과제를 다시 하기 위해 쉬어야할 시간을 표시한 양의 정수

출력: 모든 과제를 끝내는데 필요한 최소 시간을 표시한 정수

 

문제 요약: 입력으로 주어지는 리스트는 과제가 나열되어 있다. ['A', 'A', 'A'] 라면, A라는 과제가 3개 있는 것이고, 각 과제는 같은 단위 시간이 걸려서, 3이라는 시간이 걸린다. 그런데, 주어진 n은 같은 과제를 다시 하는데 필요한 쉬는 시간이다. 즉, ['A', 'A', 'A'] 의 n=2 라면 실제로는 3이 아니라 ['A', 휴식, 휴식, 'A', 휴식, 휴식, 'A'] 해서 7이라는 시간이 걸리게 된다.

단, 'A', 'B' 처럼 서로 다른 과제는 붙어서 수행할 수 있다.

즉, ['A', 'A', 'A', 'B', 'B']라면 ['A', 'B', 휴식, 'A', 'B', 휴식, 'A'] 이 될 수 있어 똑같이 7이라는 시간 안에 과제를 끝낼 수 있다.

 

유의 사항: 

생각 과정

input 리스트를 key, value 해시 구조로 정리한 다음에 가장 value가 큰 알파벳을 기준으로 maxval + n*(maxval-1)한 값을 기준으로 하고, 나머지 알파벳들을 쉬는 시간에 다 집어 넣는 형식으로 구조를 짰다.

그랬더니 오류가 나는 경우가 있었는데, 그 이유는 가장 긴 len을 가지는 과제가 하나 이상일 때 때문이었다.

즉, ['A', 'A', 'A', 'B', 'B', 'B'] 처럼, 가장 과업 갯수가 많은 과제가 2개 이상이라면, 쉬는 시간 안에 다 들어가지 못하고 뒤에 붙여야 하는 과제가 생기게 된다. ['A', 'B', 휴식, 'A', 'B', 휴식, 'A'] 후에도 'B' 하나게 남게 된다. 

풀이

 

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        if n == 0:
            return len(tasks)
        ans = 0
        dic = {}
        for i in tasks:
            dic[i] = dic.get(i,0) + 1
        
        counts_list = [dic[task] for task in dic]
        max_count = max(counts_list)
        max_count_tasks = counts_list.count(max_count)
        ans =  max_count + (max_count-1)*n +(max_count_tasks) - 1
        return max(len(tasks), ans)