[백준]1374번 강의실 - C/C++

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

1374번: 강의실

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

---

 

    그리디 문제의 대표적인 유형으로 주어진 시간에 따른 답을 구하는 문제이다.

 

    가장 간단하게 생각하면 시작 시간 순서로 정렬을 한 다음 강의실 1번에서 강의할 수 있는 강의 다 체크하고 강의실 2번.. 해서 n개의 강의가 모두 체크될 때까지 n번 강의실을 생성하면 된다.

하지만 이 방법은 시간초과가 나는데 이는 최악의 상황을 가정하면 모두 중복되는 시간을 가진 강의실 MAX_N(100000) 개가 나온다면 O(N * N)의 시간 복잡도를 가지게 되어 시간 초과가 나게 된다.

 

    그렇기 때문에 수업 종료 시간을 키로 가지는 우선순위큐를 생성하여 시작 시간에 따라 정렬된 배열에 대해 시작 시간이 현재 가장 빨리 끝나는 강의보다 먼저 시작해야 하면 강의실이 하나 더 필요하고 그렇지 않다면 그 강의실에서 수업을 진행하면 된다. 어떠한 강의실에 강의가 추가가 되었는지와는 상관없이 새로 추가된 강의가 그 강의실에서 종료시간이 가장 느리므로 우선순위 큐에 해당 강의의 종료시간을 추가해주어야 한다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int n;

pair <int, int> arr[100001];
priority_queue <int,vector<int>,greater<int>> pq;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int temp,cur,room=0;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp >> arr[i].first >> arr[i].second;
	}

	sort(arr,arr+n);
	for (int i = 0; i < n; i++) {
		if (pq.size()) {
			if (pq.top() > arr[i].first) 
				room++;
			else 
				pq.pop();
		}
		else
			room++;

		pq.push(arr[i].second);
	}
	cout << room;
}

---

    한창 코딩을 할 때는 시간 복잡도 계산을 하고 들어갔는데 이 문제가 쉬워 보여 위에서 설명한 처음 방법과 같이 하면 되겠다~ 생각하며 했더니 바로 시간초과가 떠버렸다. 문제를 한창 풀때는 유의해야 할 것들을 자연스럽게 먼저 고려하고 들어갔는데 많이 감이 죽은 것 같다!

    저번 학기는 전공을 6과목을 들어서 복습에 과제 폭탄에 코딩 문제를 풀 시간이 없었는데 이제 남은 학기는 많아봐야 전공이 3개에 그리 힘든 과목도 없으니 매일매일 문제를 계속 풀며 감을 유지해야겠다!

    이번 방학 때 7월 중에는 자바를 공부하고 8월 중에 앱이나 웹을 만드는 것이 어떨까 생각했다. 이때 아니면 자바를 언제 또 해볼까 싶고 또 안드로이드 앱을 만들면 코틀린이 자바랑 비슷하니깐 덕을 좀 보지 않을까 싶다!