[G5] 백준 1374번 강의실 C++ 그리디 알고리즘, 정렬, 우선순위 큐

리뷰

 

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

간단한 정렬 + 우선순위 큐 문제

 

 

전역 변수

• n : 강의의 개수를 저장할 변수
• ans : 정답을 저장할 변수
• T : 강의의 시작 시간 st와 종료 시간 et를 정의할 구조체, et를 기준으로 오름차순 정렬한다.
• lst : 강의 정보를 저장할 T타입 배열
• pq : 강의 정보를 저장할 T타입 우선순위 큐

 

함수

1. cmp

bool cmp(const T& left, const T& right)

 

정렬 시 사용하기 위한 커스텀 비교 함수

1. 매개 변수로 T타입 변수 2개를 각각 left, right로 전달 받는다.
2. right의 st가 left의 st보다 크다면 true를 리턴하여 두 요소의 순서를 바꾸어 준다.

 

문제풀이

1. n값을 입력 받고, n개의 요소를 입력 받아 lst배열에 저장해 준다.
2. sort함수를 통해 lst배열을 cmp함수를 기준으로 정렬해 준다.
3. 정렬 후의 n개의 요소를 순회하며 현재 요소의 st를 변수 time에 저장해 주고, pq에 현재 요소를 push해준다.
4. pq가 빌 때 까지 pq의 첫 번째 요소의 et가 time이하라면 pq에서 해당 요소를 빼내어 준다.
5. 현재 pq의 size와 ans를 비교해 더 큰 값으로 ans에 저장해 준다.
6. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 입력 받은 강의 번호는 굳이 저장해 줄 필요가 없다.

 

정답 코드

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

int n, ans;
struct T {
	int st, et;
	bool operator<(const T& other) const {
		return et > other.et;
	}
};
T lst[100000];
priority_queue<T> pq;

bool cmp(const T& left, const T& right) {
	return left.st < right.st;
}

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a, b, c; cin >> a >> b >> c;
		lst[i] = { b, c };
	}

	sort(lst, lst + n, cmp);
	for (int i = 0; i < n; ++i) {
		int time = lst[i].st;
		pq.push(lst[i]);
		while (!pq.empty() && pq.top().et <= time) pq.pop();
		ans = max(ans, (int)pq.size());
	}
	cout << ans;
}