[leetcode][621] Task Scheduler

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

---

tasks들이 주어질 때 같은 task(같은 알파벳)은 쿨다운 n이 지나기 전까지 실행이 불가능하다고 하자.

CPU가 tasks들을 모두 완료하기 위해 걸리는 최소 시간을 구해라.

---

문제의 핵심은 가장 많이 나온 task가 가장 많은 idle 을 만들 수 있다는 것이다.

따라서 가장 많이 나온 task로 idle 수를 구한 다음 남은 task 들을 idle에 최대한 채워넣는걸 목표로 한다.

 

tasks = { A, A, A, B, B }, n = 2 일 때를 생각해보자.

쿨다운 n은 동일한 task가 가장 많은 수와 관련이 있다.

A _ _ A _ _ A

위의 경우 A가 3개, B가 2개 이므로 A만 채웠을 때 idle(빈 칸)이 4가 될 것이다.

B는 idle들 사이에 넣어주면 된다.

A B _ A B _ A

따라서 정답은 7이 된다.

 

 

여기서 B를 넣기 전(가장 많이 나온 task로 idle을 구할 때) idle의 총 수를 구할 수 있다.

idle 수 = (가장 많이 나온 task 수 - 1) x n

task 수 - 1을 한 이유는 idle은 task들 사이에만 나오기 때문이다.

이 idle에 남은 task들을 집어넣는다고 생각하면 된다. 집어넣으면서 남은 idle 수를 갱신한 뒤,

최종 정답은 task들의 수 + 남은 idle 수가 된다.

 

이제 남은 task들을 idle에 집어넣으면서 idle 수를 갱신하는 걸 보자.

tasks = { A, A, A, B, B, B }, n = 2 일 때를 보자.

A B _ A B _ A B

idle 빈칸 생성은 같지만 B가 넣어질 때도 쿨다운은 유지해야 하므로 마지만 B는 idle에 넣을 수 없다.

따라서 task i(i는 알파벳 중 하나)를 idle에 끼워넣는다고 할 때 감소되는 idle 수는 min(i task 수, 가장 많이 나온 task 수 -1 ) 과 같다.

위의 예시에서 i를 B라 하면 B task를 idle에 넣는다면 3(B 개수), 2(가장 많이 나온 task(A)의 수 - 1)의 최소값인 2가 감소되서 idle 수는 4에서 2가된다.

모든 task 알파벳을 탐색하며 남은 idle의 수를 갱신한 뒤 tasks 수(알파벳 수 아님) + idle 수가 정답이 된다.

 

이 때, idle 수는 음수가 될 수 없다.

만약 idle이 음수가 되면 남은 task들은 현재까지 세팅된 task 스케쥴 사이 사이에 들어가면 쿨다운 조건을 만족한다.

 

시간 복잡도는 O(N). N=|tasks|

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/621.%20Task%20Scheduler.cpp

---

 

간만에 손으로 끄적이면서 알고리즘 정리하고 풀었는데 생각정리가 잘되고 코딩할 때는 미리 적어둔 수식만 이용하면 되서 편했다.

손으로 먼저 풀어보기. 중요한듯