621. Task Scheduler ☆☆★★★

621. Task Scheduler

 

문제 설명

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n.

해석:

• 너는 CPU 작업 목록 tasks를 받는다.
• 각각의 작업은 A~Z 중 하나의 알파벳으로 표시되어 있다.
• 그리고 숫자 n도 함께 주어진다.

---

Each CPU interval can be idle or allow the completion of one task.

해석:

• CPU는 매 시간마다 하나의 작업을 할 수 있다.
• 또는 아무 작업도 하지 않고 **idle(쉬는 상태)**일 수 있다.

---

Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

해석:

• 작업들은 어떤 순서로든 처리할 수 있다.
• 하지만 같은 작업(A, B 등)을 다시 실행하려면 최소 n 칸만큼 기다려야 한다.

---

Return the minimum number of CPU intervals required to complete all tasks.

해석:

• 모든 작업을 끝내는 데 걸리는 최소 CPU 시간(칸 수)을 리턴하라.

---

Example 1

Input: tasks = ["A","A","A","B","B","B"], n = 2

해석:

• 작업은 A 3개, B 3개.
• 같은 작업(A끼리, B끼리)은 실행할 때 사이에 최소 2칸 거리를 둬야 한다.

---

Output: 8

해석:

최적의 작업 순서로 8칸에 모든 작업을 완료할 수 있다.

---

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

해석:

• 작업 순서 예시: A 실행 → B 실행 → (아무것도 할 수 없어서) idle → A 실행 → B 실행 → idle → A 실행 → B 실행

---

After completing task A, you must wait two intervals before doing A again.

해석:

• A를 한번 실행하고 나면, 다시 A를 실행하려면 2칸을 기다려야 한다.

---

The same applies to task B.

해석:

• B도 똑같다. B를 하고 나면 B 다시 하려면 2칸 쉬어야 한다.

---

In the 3rd interval, neither A nor B can be done, so you idle.

해석:

• 3번째 칸에서는 A나 B 둘 다 못 하니까 CPU가 idle로 쉰다.

---

By the 4th interval, you can do A again as 2 intervals have passed.

해석:

• 4번째 칸에서는, 이전에 A한지 2칸이 지났으니까 A를 다시 할 수 있다.

---

Example 2

Input: tasks = ["A","C","A","B","D","B"], n = 1

해석:

• 작업: A, C, A, B, D, B (총 6개)
• 같은 작업끼리는 최소 1칸 이상 비워야 한다.

---

Output: 6

해석:

• 6칸 안에 모든 작업을 완료할 수 있다. (idle 없이)

---

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

해석:

• 작업 순서 예시: A → B → C → D → A → B

(각 같은 작업(A, B)이 1칸 이상 띄어져서 조건 만족)

---

Example 3

Input: tasks = ["A","A","A", "B","B","B"], n = 3

해석:

• 작업: A 3개, B 3개
• 같은 작업(A끼리, B끼리) 사이에 3칸 비워야 함.

---

Output: 10

해석:

• 최소 10칸이 필요하다.

---

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

해석:

• 작업 순서 예시: A → B → idle → idle → A → B → idle → idle → A → B
• idle이 많이 껴야만 A와 B를 3칸 이상 띄울 수 있다.

---

Constraint

Constraints:

• 1 <= tasks.length <= 10,000
• tasks[i]는 대문자 영어 알파벳이다.
• 0 <= n <= 100

해석:

• tasks 배열의 크기는 1~10,000개 사이
• 각 task는 A~Z 알파벳
• n은 0~100 사이 값

---

🎯 핵심 요약

"같은 작업(A, B 등)을 다시 실행할 때 최소 n칸 이상을 띄워야 하고,
idle(쉼)을 할 수도 있다.
최소한의 총 시간을 구하는 문제다."

 

✅ 이 문제 푸는 핵심 아이디어

1. 가장 많이 등장하는 작업(A, B 같은 거)을 기준으로 스케줄을 잡는다.

✅ 가장 많이 등장하는 작업들이 제일 빡빡하게 자리를 차지하게 되니까, 이걸 중심으로 스케줄을 짜야 해.

---

2. 공식은 이렇게 계산한다:

최소 필요한 시간 = (최대 빈도−1) × (n+1) + 최대 빈도 작업 수

• 최대 빈도 = 가장 많이 등장한 task의 개수
• n = 쿨다운 시간
• +1은 같은 작업끼리 간격에 다른 작업도 끼워 넣을 수 있다는 의미
• 최대 빈도 작업 수 = 최대 빈도를 가진 작업(A, B 등)이 여러 개일 수도 있으니까 추가해줘야 해

---

3. 그리고 마지막으로!

• 계산한 값이 < 전체 작업 수(tasks.length)보다 작으면 → 그냥 전체 작업 수를 리턴
• (idle이 필요 없는 경우)

---

✨ 공식 요약

 

최소 시간 = max(전체 작업 개수, (최대 빈도 - 1) * (n + 1) + 최대 빈도 작업 수)

---

🔥 그럼 코드로 쓰면 이렇게 된다

from collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        max_freq = max(count.values())  # 가장 많이 등장한 task의 빈도
        max_count = sum(1 for v in count.values() if v == max_freq)  # 최대 빈도를 가진 작업 수

        # 공식 적용
        intervals = (max_freq - 1) * (n + 1) + max_count

        # 전체 작업 수랑 비교해서 큰 값을 리턴
        return max(len(tasks), intervals)

---

✅ 쉽게 흐름 정리

단계	설명
1	task별로 몇 번 나오는지 센다
2	가장 많이 나온 작업을 찾는다
3	그걸 중심으로 최소 시간 계산한다
4	전체 작업 개수보다 작으면 전체 작업 개수가 답이다

---

🎯 한 줄 요약

"가장 많이 나온 작업을 기준으로 스케줄 간격을 잡고, 필요하면 idle을 채워서 최소 시간을 만든다!"

 

---

✨ 예제 적용

Input: tasks = ["A","A","A","B","B","B"], n = 2

• A: 3번
• B: 3번
• max_freq = 3
• max_count = 2

계산:

(3−1)×(2+1)+2=8

✅ 답: 8

(딱 맞지!)

---

🔥 최종 요약

공식	설명
(최대빈도-1) x (n+1) + (최대빈도 작업 수)	idle 고려한 최소 작업 칸 계산
결과는 tasks 총 개수랑 비교해서 큰 값 사용	idle이 필요 없는 경우 커버

 

🔥 직관적으로 풀어보자

예를 들어보자:

• 가장 많이 나오는 작업이 A, 3번 있다고 해봐 (A A A)
• 쿨다운 시간 n = 2

---

1. 가장 많은 작업을 "기둥"으로 생각해

A를 이렇게 배치하고 싶어:

A _ _ A _ _ A

• A → 2칸 띄우고 → A → 2칸 띄우고 → A
• n = 2니까 A와 A 사이에 반드시 2칸 비워야 함.

---

2. A끼리 사이 간격은 (n)칸 → 구간은 (n+1)칸

• 한 A를 놓으면, 그 뒤에는 A + (n칸의 다른 작업 또는 idle) 필요.
• 이걸 하나의 블록처럼 보면 → (n+1) 길이의 블록이 필요해.

즉, A 하나를 처리하고 → (n+1) 길이의 공간을 필요로 해.

---

3. (max_freq - 1) 블록

• 마지막 A는 끝에 오니까 뒤에 쿨다운 필요 없음.
• 그래서 (A 개수 - 1) 만큼만 (n+1) 블록이 필요.

즉,
3개의 A라면 →
2개 구간 필요:

A _ _ A _ _ A

(2개 구간, 마지막 A는 쿨다운 필요 없음)

✅ 그래서 (max_freq - 1)임.

---

4. 빈칸 채우기

그 빈칸들에:

• 다른 작업(B, C 등)이 들어가면 좋고,
• 만약 아무것도 없으면 idle로 비워야 해.

---

5. 마지막에 최대빈도 작업 수 추가

• 만약 A처럼 최대빈도인 작업이 여러 개 있으면(B도 A만큼 나오면)
• 마지막에 그냥 A, B를 같이 넣어야 함.

예시:

• A: 3번
• B: 3번

A B _ A B _ A B

• 여기서는 A와 B를 같이 기둥처럼 세우게 됨.
• 그래서 최대빈도 작업 수만큼 추가로 더해야 해.

✅ 그래서 공식이: (최대빈도−1)×(n+1)+최대빈도 작업 수 이 되는 거야!

---

🎯 한 줄 요약

"(최대빈도 - 1)개의 (n+1) 길이 블록을 만들고,
마지막에 최대빈도 작업 수만큼 덧붙인다!"

 

---

✨ 그림 요약

단계	설명
작업 최대빈도 만큼 뼈대 세움	A _ _ A _ _ A
A 사이에 (n)칸 비워야 해서 (n+1) 블록 사용	블록 크기 = (n+1)
마지막 A는 뒤에 쉬는 거 필요 없음	그래서 (max_freq - 1)개만 계산
같은 최대빈도 작업 수만큼 추가	A, B, C 같은 애들이 같이

---

🔥 예제 다시 풀어보자

Input:
tasks = ["A","A","A","B","B","B"], n = 2

• A: 3번
• B: 3번
• max_freq = 3
• max_count = 2

계산:

(3−1)×(2+1)+2=8

결과 8칸!

A B idle A B idle A B

딱 맞아. ✅

---

✨ 결론

• max_freq - 1 → 구간 수
• n + 1 → 각 구간 길이
• max_count → 마지막 칸에 최대빈도 작업 수만큼 추가

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # max((테스크의 최대 반복 개수 -1)*(인터벌 개수+1) + (최대 반복 개수를 가지는 테스트 수), 총 테스트 수)

        # 테스크의 최대 반복 개수
        Ctasks = Counter(tasks)
        maxFreq = max(Ctasks.values())

        # 최대 반복 개수를 가지는 테스트 수
        nTasks_with_maxFreq = sum([1 for v in Ctasks.values() if v==maxFreq])

        return max((maxFreq-1) * (n+1) + nTasks_with_maxFreq, len(tasks))