문제

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

---

풀이

시간초과

N의 크기가 최대 10만이기 때문에, O(N^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> arr;
vector<stack<pii>> v;
int cnt = 0;

// 새로운 스택 생성하여 배열에 추가 
void addStack(pii element) {
	stack<pii> st;
	st.push(element);
	cnt++;
	v.push_back(st);
}

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

	cin >> N;

	for(int i = 0; i < N; i++){
		int s, e;
		cin >> s >> e; 
		arr.push_back({s, e});
	}

	// 	시작 시간을 기준으로 정렬
	sort(arr.begin(), arr.end());

	// 스택 배열 초기화
	addStack(arr[0]);
	
	for(int i = 1; i < N; i++){
		int start = arr[i].first;

		// 현재 회의를 배정할 수 있는 스택 찾기
		bool found = false;
		for(int j = 0; j < v.size(); j++){
			int end = v[j].top().second;
			if(start >= end){
				v[j].push(arr[i]);
				found = true;
				break;
			}
		}

		// 배정 가능한 스택이 없으면 새로 생성
		if(!found) addStack(arr[i]);
	}

	cout << v.size() << endl; 
	
	return 0;
}

여러 개의 스택을 저장하는 배열 v를 단순히 순차 탐색하고 있기 때문에, 위의 코드의 시간복잡도는 O(N^2)이다.

O(logN)의 시간복잡도를 갖는 대표적인 자료구조가 힙을 기반으로 한 '우선순위 큐'이므로, 이를 이용해서 시간복잡도를 줄여보자!

우선순위 큐

'하나의 회의실에서는 하나의 회의만 진행할 수 있다'는 사실에 더 포커스를 맞췄으면, 아이디어를 떠올릴 수 있었을 거 같다.

굳이 첫번째 풀이처럼 스택에 이전 회의들까지 전부 저장해둘 필요가 없다.

종료 시간을 기준으로 한 최소 힙 ans를 만들어서

"이전 회의의 종료 시간 <= 현재 회의의 시작 시간" 조건을 만족시키면

이전 회의는 제거하고 현재 회의를 추가함으로써 가장 최신의 회의 정보만 우선순위 큐에 저장해두면 된다.

그리고 최종적으로 ans 우선순위 큐의 크기가 필요한 회의실의 최소 개수가 된다.

#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;

// 회의 시작 시간을 기준으로 한 최소 힙
priority_queue<pii, vector<pii>, greater<>> pq;

// 회의 종료 시간을 기준으로 한 최소 힙 
priority_queue<int, vector<int>, greater<>> ans;

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

	cin >> N;

	for(int i = 0; i < N; i++){
		int s, e;
		cin >> s >> e; 
		pq.push({s, e});
	}

	// 시작 시간이 가장 빠른 원소 추가 
	ans.push(pq.top().second);
	pq.pop();

	while(!pq.empty()){
		pii now = pq.top();
		int prevEndTime = ans.top();
		int curStartTime = now.first;

		if(prevEndTime <= curStartTime){
        	ans.pop(); // 이전 원소 제거 
			ans.push(now.second); // 새 원소 추가 
		}else{
			ans.push(now.second);
		}

		pq.pop();
	}

	cout << ans.size(); 
	
	return 0;
}

N개의 회의에 대해서 우선순위 큐에 원소를 삽입 또는 삭제하고 있으므로, 총 시간복잡도는 O(NlogN)이라고 볼 수 있다.

그리고 시작 시간이 빠른 회의부터 우선적으로 배정한다는 점에서 그리디 알고리즘으로 분류할 수 있다!