블록들의 목록이 주어졌다고 가정해 봅시다. blocks[i] = t라면 i번째 블록을 완성하는 데 t 단위의 시간이 필요하다는 의미입니다. 각 블록은 정확히 한 명의 작업자만이 지을 수 있으며, 작업자 한 명은 두 명의 작업자로 분열하거나 블록 하나를 지은 뒤 퇴장하는 두 가지 행동 중 하나를 선택할 수 있습니다. 이때 작업자 하나를 둘로 나누는 데 걸리는 시간은 split이라는 값으로 주어집니다.
예를 들어 입력이 blocks = [1, 2], split = 5라고 해보겠습니다. 이 경우 출력은 7이 됩니다. 작업자를 5단위의 시간을 들여 두 명으로 나눈 뒤 각각에게 블록 하나씩을 배정하면, 총 비용은 5 + max(1, 2) = 7이 되기 때문입니다.
접근 방법
이 문제는 최소 힙(min-heap) 기반의 우선순위 큐를 활용하는 그리디 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 매번 가장 작은 두 개의 값을 꺼내 병합하는 것으로, 허프만 코딩(Huffman Coding)과 유사한 방식입니다. 병합할 때마다 분열 비용 split을 더해 다시 큐에 넣는 과정을 반복하면, 마지막에 남는 값이 곧 최소 건설 시간이 됩니다.
구체적인 해결 절차는 다음과 같습니다.
- 최소 힙으로 동작하는 우선순위 큐 pq를 정의합니다.
- 모든 블록의 건설 시간을 pq에 삽입합니다.
- pq의 크기가 1보다 큰 동안 다음을 반복합니다.
- pq에서 가장 작은 원소를 제거합니다.
- x에 현재 pq의 최상단 원소(두 번째로 작은 값)를 저장한 뒤 제거합니다.
- split + x 값을 pq에 다시 삽입합니다.
- 반복이 끝나면 pq의 최상단 원소를 반환합니다. 이것이 곧 최소 건설 시간입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minBuildTime(vector<int>& blocks, int split) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < blocks.size(); i++)
pq.push(blocks[i]);
while (pq.size() > 1) {
pq.pop();
int x = pq.top();
pq.pop();
pq.push(split + x);
}
return pq.top();
}
};
main(){
Solution ob;
vector<int> v = {1,2};
cout << (ob.minBuildTime(v, 5));
}
실행 결과
입력:
{1,2}, 5
출력:
7
동작 원리 살펴보기
위 예제에서 우선순위 큐에는 처음에 1과 2가 들어갑니다. 첫 번째 반복에서 가장 작은 값 1이 먼저 제거되고, 다음으로 작은 값 2가 x에 저장된 뒤 제거됩니다. 이후 split + x인 5 + 2 = 7이 큐에 다시 삽입됩니다. 이제 큐에는 7 하나만 남았으므로 반복이 종료되며, 최종 결과로 7이 반환됩니다.
이 알고리즘의 시간 복잡도는 O(n log n)입니다. 여기서 n은 블록의 개수이며, 병합 연산마다 힙 연산에 log n의 시간이 걸리기 때문입니다. 공간 복잡도는 모든 블록을 우선순위 큐에 저장하므로 O(n)입니다.