백준 BOJ 1374 - 강의실

백랜디 도중에 만난 문제

세종정보올림피아드에서 비슷한 유형의 문제를 접했던 기억이 있어서

"케이크처럼" 쉽게 풀어보았다.

 

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

1374번: 강의실

강의 시작시간과 종료시간을 기준으로 탐색하면 10억번의 탐색을 필요로 하고,

시간초과를 받음이 매우 직관적으로 보인다

 

강의의 시작시간과 종료시간 사이에는 그 강의가 항상 있음이 보장 되기 때문에,

그 중간 시간에 대해서 탐색할 필요가 없다는게 시간 절약 방법의 핵심.

굉장히 당연한 말을 한 것 같지만 이게 이 문제의 핵심이라고 생각한다.

 

강의의 시작점과 끝 점 모두 set 자료구조에 저장한다.

set 자료구조는 값이 중복으로 들어가는걸 막으니까

그냥 강의가 시작하거나 끝나는 모든 시간점이 set 자료구조 안에 들어가게 된다.

 

그리고 그 시간에 강의가 몇개 시작하고, 몇개 끝나는지를 관리해주어야 한다.

O(logN)의 Map 을 사용해도 되지만, 나는 그냥 O(1) 의 Unordered_map 을 사용했다.

 

set 에서 임의의 시간점 A를 뽑았고,

기존에 B개의 강의가 진행되고 있었으며,

A 시간에 C개의 강의가 새로 진행되고

D개의 강의가 끝난다면

 

A 시간대부터 A 바로 뒤의 A' 시간대 까지는

반드시 B+C-D개의 강의가 진행중임이 보장된다.

 

즉 set 자료형을 순회하면서 이 B를

B+C-D 로 갱신하면서 최댓값을 기록하면

모든 구간에 대한 강의 수를 탐색할수 있기 때문에

정답을 얻을 수 있다.

시간복잡도는 set 자료구조가 logN시간에 탐색하므로

O(NlogN)

 

#include <bits/stdc++.h>
using namespace std;

set<int> s;
unordered_map<int,int> st;
unordered_map<int,int> ed;

int main(){
	int N;
	int a,b,c;
	cin >> N;
	
	for(int i=0; i<N; i++){
		cin >> a >> b >> c;
		s.insert(b);
		s.insert(c);
		st[b]++;
		ed[c]++;
	}
	
	int val = 0;
	int ans = 0;
	for(auto k : s){
		val += st[k];
		val -= ed[k];
		
		ans = max(ans,val);
	}
	
	cout << ans;
	return 0;
}