강의실 배정

YoungJae·2022년 7월 1일
0

Boj

목록 보기
8/14

문제

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

참고

https://wooono.tistory.com/393
https://everydayyy.tistory.com/20?category=1039746
https://j3sung.tistory.com/497
https://velog.io/@ss-won/PS-%EB%B0%B1%EC%A4%80-11000-%EA%B0%95%EC%9D%98%EC%8B%A4-%EB%B0%B0%EC%A0%95-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4

해당 문제는 입력으로 주어진 N개의 수업의 시작과 종료시간을 고려해, 모든 수업을 진행하기 위해 필요한 최소 강의실의 수를 출력하는 문제이다.

  1. 처음 문제를 보고 백준의 "회의실 배정" 문제가 생각나서, 거의 그대로 접근했다.
    즉, 문제의 의미를 제대로 파악하지 못하고 잘못된 접근을 했었다.

    하지만 게시판에 있는 반례를 통해 문제에서 묻는 바에 대해 제대로 이해한 다음, 머릿속이 수렁에 빠지게 됐다.

주어진 입력의 크기는 2*10^5으로, 문제의 시간제한을 만족하기 위해서는 최소한 O(NlogN) 이하의 알고리즘을 작성해야한다.
하지만 O(NlogN) 알고리즘을 통해 강의실의 최소값을 출력할 구조가 도통 생각이 나지 않았다.

이전의 "회의실 배정" 문제를 풀때 접근법을 활용하자니 최악의 경우 O(N^2)을 가지게 된다.

따라서 위와 같은 여러 블로그를 참고하여 O(NlogN) 시간복잡도를 가지며 강의실의 최소값을 출력하는 방법에 대해 알아봤다.

  1. 문제 풀이를 위해 가장 핵심이 되는 것은 priority_queue에 대한 이해이다.

    가장 중요한 부분만 정리하면,
    1) priority_queue는 트리의 모든 레벨에서 항상 부모노드가 (좌/우) 자식노드보다 큰 값을 가진다.(max_heap 기준)
    2) 따라서 push/pop 연산시 O(logN)의 시간복잡도를 가진다.

    다시 문제로 돌아오면, 해당 문제는 이전에 푼 "회의실 배정" 문제와 다르게 접근해야 한다.
    모든 강의 중 가장 빨리 시작하는 수업을 기준으로 그리디 알고리즘을 적용해야 한다.
    해당 문제에서 적용한 그리디 알고리즘의 로직은 다음과 같다.(min_heap의 노드(=성분)을 사용하는 강의실로 생각)

    1) 비어있는 priority_queue(min_heap)에 가장 먼저 시작하는 수업의 종료시간을 push한다.

    2) 다음에 진행되는 수업의 시작시간을 min_heap의 루트노드에 있는 종료시간과 비교한다.

    만약, 다음에 진행되는 수업의 시작시간이 min_heap의 루트노드에 있는 종료시간 보다 작으면 해당 수업의 종료시간을 min_heap에 그대로 push하고,

    같거나 크면 루트노드를 pop하고 해당 수업의 종료시간을 min_heap에 그대로 push한다.

    3) 모든 수업에 대해 위의 과정을 반복한다.

    해당 알고리즘의 핵심 아이디어는 1) 모든 수업을 진행하기 위해 강의실을 최소로 사용하기 위해서는 매번 수업을 사용하는 강의실 중에 "종료시간이 빠른 강의실"과 비교해야 한다는 점과(따라서 min_heap 사용), 2) 시간복잡도가 강의의 수 N * min_heap에서 매번 진행되는 연산수 NlogN = NlogN 을 만족한다는 점이다.

    따라서 위의 로직을 통해 모든 수업에 대해 연산을 수행하면 최종적으로 min_heap에 남은 성분의 수는 N개의 모든 수업을 진행하기 위해 필요한 "최소 강의실의 수"를 의미하게 된다.

    그리고 위의 로직은 사전에 모든 수업의 시작시간과 종료시간에 대해 각각 오름차순 정렬을 필요로 한다.

solved.ac 티어를 최대한 의식하지 않으려고 하지만, 골드 5 수준의 문제를 푸는 과정에서 priority_queue와 같은 자료구조의 응용력 부족을 통해 아직 실력이 많이 부족하다는 것을 느껴졌다.

코딩테스트에서 안정적으로 합격하기 위해서는 다양한 유형에 대해 골드 수준의 문제를 풀 수 있어야 하기 때문에, 이러한 느낌을 자양분으로 삼아서 조금이나마 더 앞으로 나가도록 노력해야겠다.

위의 내용을 모두 고려한 전체 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);

	int n, a, b, min = 2147000000;
	vector<pair<int, int> > class_list;
	priority_queue<int, vector<int>, greater<int> > pq;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		class_list.push_back(make_pair(a, b));
	}

	sort(class_list.begin(), class_list.end());

	pq.push(class_list[0].second);
	for (int i = 1; i < n; i++) {
		if (class_list[i].first >= pq.top()) {
			pq.pop();
		}

		pq.push(class_list[i].second);
	}

	cout << pq.size() << "\n";
	return 0;
}
profile
코딩테스트 넘어서기

0개의 댓글