쿨타임이 있는 작업 배치
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
공장의 기계 한 대가 처리해야 할 작업 목록이 문자열 tasks로 주어집니다. 각 글자(영어 대문자)는 작업의 종류이고, 작업 하나는 정확히
1단위 시간이 걸립니다. 작업은 원하는 순서로 처리할 수 있고, 매 단위 시간마다 기계는 작업 하나를 처리하거나 쉽니다.
같은 종류의 작업을 연달아 하면 기계가 과열되므로, 같은 종류의 두 작업 사이에는 적어도 n단위 시간이 있어야 합니다.
즉 어떤 종류의 작업을 시각 에 처리했다면, 같은 종류의 다음 작업은 시각 이후에만 처리할 수 있습니다.
모든 작업을 끝내는 데 필요한 최소 시간(쉬는 시간 포함)을 반환하세요.
입출력 예
| tasks | n | result |
|---|---|---|
"AAABBB" | 2 | 8 |
"AAABBB" | 0 | 6 |
"AAAAAABCDEFG" | 2 | 16 |
입출력 예 설명
예 1 — A B (쉼) A B (쉼) A B 순서로 처리하면 8단위 시간이 걸리고, 이보다 빠를 수 없습니다.
예 2 — 간격 제한이 없으므로 쉬지 않고 6단위 시간에 끝납니다.
예 3 — A B C A D E A F G A (쉼) (쉼) A (쉼) (쉼) A처럼 A 여섯 개 사이를 다른 작업과 쉬는 시간으로 채우면 16단위 시간입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(tasks: string, n: int) → long
제한 사항
-
tasks.length,tasks는 영어 대문자로만 이루어져 있습니다. -
n
기대 복잡도
- 시간
- O(L)
- 공간
- O(1)
입출력 예
| tasks | n | 기대 출력 |
|---|---|---|
"AAABBB" | 2 | 8 |
"AAABBB" | 0 | 6 |
"AAAAAABCDEFG" | 2 | 16 |
힌트
힌트
시간을 한 단위씩 흘려 보내며 시뮬레이션하면, 쉬는 시간이 많을 때 전체 시간이 약 단위까지 늘어나 시간 초과가 납니다.
가장 많이 나온 작업의 개수를 , 개수가 인 작업 종류의 수를 라고 해 보세요. 가장 많은 작업을 개의 "칸"의 시작으로 두면, 앞의 칸은 각각 길이가 이어야 하고 마지막 칸에는 개수가 인 종류 개가 들어갑니다.
다른 작업이 이 빈칸을 다 채우고도 남으면 쉬는 시간 없이 끝나므로, 답은 이 값과 tasks.length 중 큰 값입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |