LeetCode 621. Task Scheduler

파이썬 알고리즘 인터뷰80번(리트코드 621번) Task Scheduler
https://leetcode.com/problems/task-scheduler/

나의 풀이1

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        result = 0
        cooling = collections.defaultdict(lambda: -n-1)
        counts = collections.Counter(tasks)
        remain = len(tasks)
        
        while remain > 0:
            idle = True
            for task in counts.most_common():
                if result - cooling[task[0]] <= n or counts[task[0]] == 0:
                    continue
                else:
                    counts[task[0]] -= 1
                    cooling[task[0]] = result
                    result += 1
                    remain -= 1
                    idle = False
                    break
            if idle:
                result += 1
        return result
        

• 출현 횟수가 가장 많은 문자를 꺼내 넣고, 넣은 지점을 기록한다.
• 현재 고른 문자가 이전에 넣은 지점과 비교해서 아직 못 넣는 상태면 다음 문자를 고른다.
• 넣을 수 있는 문자가 없는 채로 한 바퀴를 모두 돌면 idle을 하나 넣어준다.
• 끝날 때까지 반복한다.
• 이 풀이는 매우 느리다.
• 개선의 여지를 생각해보니, 가장 많이 나오는 문자가 A, B로 각각 3번씩 나온다면. 나머지 문자는 어떤 문자인지 몇 번씩 나오는 지 중요하지 않다. 그런데 이 풀이는 이를 이용하지 못하고 그때 그때 남은 문자 중 가장 많이 출현하는 것을 새로 찾기 때문에 느리다.

나의 풀이2

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = collections.Counter(tasks)
        result = 0

        while counts:
            cycle = n + 1
            while cycle:
                for char, freq in counts.most_common():
                    counts[char] -= 1
                    cycle -= 1
                    result += 1
                    if counts[char] == 0:
                        del counts[char]
                    if cycle == 0:
                        break
                if counts:
                    result += cycle
                cycle = 0
        return result

• 나의 풀이1보다는 훨씬 빠르지만 나의 풀이3보다는 느리다.
• 한 사이클 단위로 생각했다. n=7이면 가장 많이 나온 문자가 A일 때 두 A 사이에 7개의 다른 문자를 넣어서 A를 포함하면 길이 8인 cycle이 반복된다.
• 이때, 자투리 문자들이 충분하지 않으면 5개만 채우고 3개는 idle이 되는 상황이 생긴다. 풀이1에서는 모든 문자의 남은 횟수를 조회 후 idle 한 개를 추가한다. 3개의 idle을 추가하려면 3번씩 모든 문자를 조회하는 것이다.
• 이와 달리 풀이2에서는 5개 채우고 나서 남는 자투리 문자가 없을 때 3개의 idle을 한 번에 추가하게 되어 좀 더 빠르다.
• 또한, 풀이1과 달리 남은 횟수가 0인 문자는 그때 그때 지워버려서 나중에 조회할 때 더 빠르다.

나의 풀이3

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = collections.Counter(tasks)
        max_freq = counts.most_common(1)[0][1]
        max_char = [key for key, val in counts.items() if val == max_freq]
        return max((n + 1) * (max_freq - 1) + len(max_char), len(tasks))

• 풀이1, 2는 공통적으로 그때 그때 남아 있는 개수를 업데이트 하며 가장 많이 남은 문자를 조사한다.
• 하지만 그럴 필요가 없다. 제일 처음에 가장 많이 등장하는 문자와 그 횟수만 알면, 나머지 문자들은 몇 번씩인지 굳이 조사할 필요가 없다.
• 원래는 이게 나의 풀이2로 시도했던 풀이이다. 처음에 len(tasks) 보다 작은 값이 나오는 엣지 케이스가 있었는데, len(tasks)값이랑 구한 값을 max처리할 생각을 하지 않고 위의 나의 풀이 2로 접근했었다.
• 이 풀이가 가장 빠르다.

나의 풀이4

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq = collections.Counter(tasks).values()
        max_freq = max(freq)
        num_of_max_freq = list(freq).count(max_freq)
        return max((n + 1) * (max_freq - 1) + num_of_max_freq, len(tasks))
       

• 나의 풀이3에서 좀 더 사람들이 자주 쓰는 표현으로 바꿈.

다른 풀이

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = collections.Counter(tasks)
        result = 0

        while True:
            sub_count = 0
            for task, _ in counts.most_common(n + 1):
                sub_count += 1
                result += 1
                counts.subtract(task)
                counts += collections.Counter() # 0 이하인 아이템 제거
            if not counts:
                break
            result += n - sub_count + 1
        
        return result

• 책 풀이인데 나의 풀이3 보다 느리고 이해가 어렵다.
• 배울 점으로 counts.most_common(n)이 아니라 counts.most_common(n + 1) 하여 마지막 부분 처리한 아이디어.
• 그리고 counts += collections.Counter() 이용하여 0 이하인 아이템 제거하는 아이디어.

배운 점

• Counter의 여러 연산에 대해 정리해보자. counts += collections.Counter() 이용하여 0 이하인 아이템 제거하는 아이디어 몰랐었음.