Funcia
Lv.2countinggreedymath

쿨타임이 있는 작업 배치

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

공장의 기계 한 대가 처리해야 할 작업 목록이 문자열 tasks로 주어집니다. 각 글자(영어 대문자)는 작업의 종류이고, 작업 하나는 정확히 1단위 시간이 걸립니다. 작업은 원하는 순서로 처리할 수 있고, 매 단위 시간마다 기계는 작업 하나를 처리하거나 쉽니다.

같은 종류의 작업을 연달아 하면 기계가 과열되므로, 같은 종류의 두 작업 사이에는 적어도 n단위 시간이 있어야 합니다. 즉 어떤 종류의 작업을 시각 tt에 처리했다면, 같은 종류의 다음 작업은 시각 t+n+1t + n + 1 이후에만 처리할 수 있습니다.

모든 작업을 끝내는 데 필요한 최소 시간(쉬는 시간 포함)을 반환하세요.

입출력 예

tasksnresult
"AAABBB"28
"AAABBB"06
"AAAAAABCDEFG"216

입출력 예 설명

예 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

제한 사항

  • 1≤1 \le tasks.length ≤1,000,000\le 1{,}000{,}000, tasks는 영어 대문자로만 이루어져 있습니다.
  • 0≤0 \le n ≤1,000\le 1{,}000

기대 복잡도

시간
O(L)
공간
O(1)

입출력 예

tasksn기대 출력
"AAABBB"28
"AAABBB"06
"AAAAAABCDEFG"216

힌트

힌트

시간을 한 단위씩 흘려 보내며 시뮬레이션하면, 쉬는 시간이 많을 때 전체 시간이 약 10910^9단위까지 늘어나 시간 초과가 납니다.

가장 많이 나온 작업의 개수를 MM, 개수가 MM인 작업 종류의 수를 cc라고 해 보세요. 가장 많은 작업을 MM개의 "칸"의 시작으로 두면, 앞의 M−1M-1칸은 각각 길이가 n+1n+1이어야 하고 마지막 칸에는 개수가 MM인 종류 cc개가 들어갑니다.

(M−1)(n+1)+c(M - 1)(n + 1) + c

다른 작업이 이 빈칸을 다 채우고도 남으면 쉬는 시간 없이 끝나므로, 답은 이 값과 tasks.length 중 큰 값입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.