CPU가 수행해야 할 작업들을 나타내는 문자 배열이 있다고 가정해 봅시다. 이 배열은 대문자 A부터 Z까지로 구성되며, 서로 다른 문자는 서로 다른 작업을 의미합니다. 작업은 원래 순서와 무관하게 수행될 수 있으며, 각 작업은 하나의 인터벌(시간 단위) 안에서 완료됩니다.
각 인터벌 동안 CPU는 하나의 작업을 처리하거나, 아무것도 하지 않고 대기(idle)할 수 있습니다. 여기서 중요한 조건은 음수가 아닌 쿨다운 간격(cooling interval) n입니다. 이는 동일한 두 작업 사이에 최소 n개의 인터벌 동안 CPU가 다른 작업을 수행하거나 쉬어야 한다는 의미입니다.
우리의 목표는 주어진 모든 작업을 완료하기 위해 CPU가 필요로 하는 최소 인터벌 수를 구하는 것입니다.
예시
입력이 [A, A, A, B, B, B]이고 n = 2인 경우를 살펴보겠습니다. 이때 출력은 8이며, 실행 순서는 다음과 같습니다.
A → B → idle → A → B → idle → A → B
해결 접근 방법
이 문제는 그리디(Greedy) 알고리즘과 우선순위 큐(Priority Queue)를 활용하여 해결할 수 있습니다. 매 사이클마다 남은 실행 횟수가 가장 많은 작업부터 우선적으로 배치하면, 전체 소요 시간을 최소화할 수 있습니다.
알고리즘 단계
맵(map) m을 생성하고, 작업 배열에 포함된 각 문자의 빈도수를 저장합니다.
우선순위 큐(priority queue) pq를 정의합니다.
m에 있는 모든 키-값 쌍을 순회하며 빈도수를 pq에 삽입합니다.
정답 변수 ans := 0, 사이클 길이 cycle := n + 1로 초기화합니다.
pq가 비어 있지 않은 동안 다음을 반복합니다:
임시 벡터 temp를 선언하고, time := 0으로 초기화합니다.
i가 0부터 cycle 미만이면서 pq가 비어 있지 않은 동안, pq의 최상단(top) 요소를 temp에 저장하고 pq에서 제거한 뒤 time을 1씩 증가시킵니다.
temp의 모든 요소에 대해 값을 1 감소시키고, 값이 0이 아닌 경우 다시 pq에 삽입합니다.
pq가 비었다면 ans에 time을 더하고, 그렇지 않으면 cycle을 더합니다.
최종적으로 ans를 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 과정을 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int leastInterval(vector<char>& t, int n) {
map <char,int> m;
for(int i =0;i<t.size();i++){
m[t[i]]++;
}
map <char, int> :: iterator i = m.begin();
priority_queue <int> pq;
while(i != m.end()){
pq.push(i->second);
i++;
}
int ans = 0;
int cycle = n + 1;
while(!pq.empty()){
vector <int> temp;
int time = 0;
for(int i = 0; !pq.empty() && i < cycle; i++){
temp.push_back(pq.top());
pq.pop();
time++;
}
for(int i = 0;i < temp.size(); i++){
temp[i]-- ;
if(temp[i])pq.push(temp[i]);
}
ans += pq.empty()? time : cycle;
}
return ans;
}
};
main(){
vector<char> v = {'A','A','A','B','B','B'};
Solution ob;
cout << (ob.leastInterval(v, 2)) ;
}입력
{'A','A','A','B','B','B'}
2출력
8
동작 원리 설명
위 예제에서 n = 2이므로 한 사이클의 길이는 n + 1 = 3입니다. 첫 번째 사이클에서는 가장 많이 남아 있는 작업인 A와 B를 차례로 실행하고, 쿨다운 규칙을 만족하기 위해 idle 한 칸을 포함해 총 3개의 인터벌을 사용합니다. 이 과정을 반복하면 A → B → idle → A → B → idle → A → B 순서로 진행되며, 마지막 사이클에서는 idle 없이 작업만 실행되므로 time(실제 사용한 인터벌 수)이 더해집니다. 결과적으로 총 8개의 인터벌이 필요하게 됩니다.
이 알고리즘의 시간 복잡도는 O(N log N)(N은 작업 개수), 공간 복잡도는 O(N)입니다.