문제 설명

task들이 주어졌을 때, 같은 task끼리는 cooling time n 이 지난후 실행할 수 있다고 한다. 이때 모든 task를 수행하는데 소요되는 최소 시간을 구하라.

풀이 및 해설

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
    
        cnt = [0]*26
        for task in tasks:
            cnt[ord(task)-ord('A')] += 1
            
        max_cnt = max(cnt)
        n_freq = cnt.count(max_cnt) # number of most frequent tasks
        
        return max( (max_cnt-1)*(n+1)+n_freq, len(tasks) )

ord(x) 함수: 문자열의 ascii 코드를 반환해주는 함수. 항상 까먹지만 항상 유용하다. 참고로 ord('a')=97 이 정도는 상식임. -> 유니코드라는 말이 있네? 아무튼 숫자로 바꿔서 처리할 때 필요한 경우가 있는데 사용하는 거

참고. chr(x) 함수: ascii 코드를 넣으면 해당하는 문자를 반환해주는 함수.

1. 각각의 task가 몇 번 수행되어야 하는지를 먼저 센다.
2. 가장 많이 수행되는 task를 기준으로 chunk를 나눈다.
3. 빈 공간에 남은 task들이 다 들어갔다고 가정한 경우와 그렇지 않은 경우를 고려하여 둘 중 최댓값으로 정답을 구한다.

[예시] A와 B가 3번씩 실행되었고 이때 쿨타임이 5라고 하자,

Scheduler: A B _ _ _ A B _ _ _ A B (12회)

max_cnt = 3: 가장 많이 실행된 task의 실행횟수가 3번이기 때문.
n_freq = 2: 가장 많이 실행된 task는 1개 이상 존재할 수 있기 때문에 몇 개나 있는지 세줌. A와 B 2개.

빈 공간에 남은 task들이 다 들어가는 경우: (max_cnt-1)*(n+1) + n_freq

✅ A B _ _ _
✅ A B _ _ _
❎ A B

max_cnt-1: ✅ 개수, 가장 많이 실행된 task 사이의 공백 개수.
n+1: ✅ chunk 하나 당 길이, task 와 빈 칸의 개수. 이해가 쉬우려면 가장 많이 실행된 task는 하나로 보고 그 이후 n 회의 쿨타임이 필요하니까 n+1 이라고 생각하면 됨.

마지막 n_freq를 더해주는 이유는, ❎ 부분을 채워주기 위함이다. 쿨타임이 필요 없는 마지막 instruction은 몇 개나 나오는지 알기 위함.

여기서는 빈 공간에 남은 instruction들이 모두 들어갈 수 있다고 본 건데, 넘치는 경우도 분명히 있을거다.

[예시] A, B, C가 3번씩 실행되었고, D가 2번 실행됨. 이때 쿨타임이 2라고 하자

Scheduler: B A D C A B D C A B C (11회)

아까 공식에 넣어서 구해보면 ( 3 - 1 ) x ( 2 + 1 ) + 3 = 9 라서 실제 구한 것보다 작다. 이유는 빈 공간에 나머지들을 다 채우고도 흘러 넘쳤기 때문.
그럴 땐 그냥 len(tasks)가 최소 수행 횟수가 된다.

task의 개수는 많아봤자 26개라는 점도 생각해볼 지점인듯.