문제

https://www.acmicpc.net/problem/12764

---

풀이

시간초과

최적화 문제를 결정 문제로 바꿔서 이분탐색으로 해결하는 파라메트릭 서치로 구현해봤는데, decision 함수에서 시간복잡도가 O(N^2)이므로 N이 최대 10만인 이 문제에서는 TLE가 발생한다.

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N; 
vector<pii> person; // 시작, 종료 시각 
vector<vector<pii>> computer; // 컴퓨터에 배정된 사람 정보 
vector<int> ans;

void savePersonNumber() {
	if(!ans.empty()) ans.clear(); 
	
	for(auto& com: computer){
		ans.push_back(com.size());
	}
}

// 컴퓨터의 개수가 x개일 때
// N명의 대기 시간이 모두 0인가? 
bool decision(int x){
	// 컴퓨터 개수 고정
	computer.resize(x);

	// i번째 컴퓨터에 i번째 사람 배정 
	for(int i = 0; i < x; i++){
		computer[i].push_back(person[i]);
	}

	// 남은 N - x 명에 대해 종료, 시작 시각 비교 
	for(int i = x; i < N; i++){
		auto now = person[i];

		bool success = false;
        
        // 주의!!!! 복사본이 아닌 원본 배열을 바꾸기 위해 & 필수 
		for(auto& com: computer){ 
			int lastIdx = com.size() - 1;

			if(com[lastIdx].second < now.first){
				com.push_back(now); 
				success = true; 
				break;
			}
		}

		if(!success) return false; 
	}
	
	savePersonNumber();
	return true; 
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N; // 최대 10만

	// 컴퓨터 이용 시작, 종료 시각 
	for(int i = 0; i < N; i++){
		int s, e;
		cin >> s >> e; 
		person.push_back({s, e});
	}

	// 시작 시간이 빠른 순으로 정렬 
	sort(person.begin(), person.end());

	int left = 1; 
	int right = N;

	while(left <= right){
		int mid = (left + right) / 2; 
		if(decision(mid)){
			right = mid - 1;
		}else{
			left = mid + 1;
		}

		for(auto& com: computer){
			if(!com.empty()) com.clear();
		}
	}

	cout << left << endl; 
	for(auto e: ans){
		cout << e << " "; 
	}
	
	return 0;
}

N명의 사람을 x개의 컴퓨터에 배정할 때, 선형이 아닌 로그 시간복잡도로 구현할 수 있는 방법이 있을까?

대표적으로 이진 탐색 트리 기반의 set, map 자료구조 또는 균형 잡힌 이진 트리인 힙 기반의 우선순위 큐 자료구조를 생각할 수 있다.

코드 개선

2개의 우선순위 큐를 이용하여 다음과 같이 구현할 수 있다.

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N; 
vector<pii> person; // 컴퓨터 이용 시작, 종료 시각

// 종료 시각, 좌석 번호 (종료 시각이 빠른 게 우선, 최소 힙)
priority_queue<pii, vector<pii>, greater<pii>> pq; 

// 비어있는 좌석 번호 (낮은 번호가 우선, 최소 힙)
priority_queue<int, vector<int>, greater<int>> seats; 

const int MAX = 100001; 
int ans[MAX]; // 각 컴퓨터의 이용자 수 

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N; // 최대 10만

	// 컴퓨터 이용 시작, 종료 시각 
	for(int i = 0; i < N; i++){
		int s, e;
		cin >> s >> e; 
		person.push_back({s, e});
	}

	// 시작 시간이 빠른 순으로 정렬 
	sort(person.begin(), person.end());

	// N명이 사용하기 위해 필요한 최소 컴퓨터 수 
	int num = 0;  
	
	for(auto& time: person){ 
		while(!pq.empty()){
			// 사용중인 사람의 종료 시각 vs. 다음으로 들어올 사람의 시작 시각
			int endTime = pq.top().first;
			int seatNum = pq.top().second; 
			int startTime = time.first; 

			// 이전 사용자가 이용을 종료한 경우 
			if(endTime < startTime){
				// 해당 좌석에 다음 사용자를 앉힌다. 
				seats.push(seatNum);
				pq.pop(); 
			}
			else break; 
		}

		// 초기 상태 또는 빈 좌석이 없을 때 
		if(seats.empty()){
			// 새 좌석을 만들어서 앉힌다. 
			pq.push({time.second, num}); 
			ans[num]++;
			num++;
		}else{
			// 빈 좌석이 있는 경우 
			// 가장 낮은 번호의 자리에 앉힌다. 
			int front = seats.top(); 
			pq.push({time.second, front});
			ans[front]++;
			seats.pop(); 
		}
	}

	cout << num << endl; 
	for(int i = 0; i < num; i++){
		cout << ans[i] << " ";
	}
	
	return 0;
}

우선순위 큐의 삽입/삭제 연산의 시간복잡도는 O(logN)이므로, 전체 시간복잡도는 O(NlogN)이 되어 제한 시간 내에 문제를 해결할 수 있다.