문제
접근 방법
처음에는 프로그래머스의 단속카메라 같은 문제라고 생각했다. 하지만 그런 방식으로 접근하면 이미 지나간 시간에 대해서는 폐기됐기에 올바른 답이 안 나온다.
단속카메라에서 그렸던 예 중 하나다. 단속카메라 방식으로 푼다면 최종적으론 초록색 위에 부분으로 조금씩 좁혀지며 4라는 값이 나올 것이다.
만약 파란색 이후에 여러 겹으로 겹친다면 어떻게 될까?
단속카메라에서 사용했던 방식대로 한다면 6개로 확인되어야 할 부분도 4개로 확인된다. (왜냐하면 반복문을 통해 이미 제거해버렸기 때문이다.)
이것을 설명하는 이유는 내가 이 방법으로 풀려다 실패해서 그랬다. 얼마 안 되는 반례는 통과하더라도 제출하면 실패했기 때문이다.
그렇다면 무슨 방법을 써야할까?
배열을 만들어두고 개수를 세어야 할까? 그러기엔 10^9까지 확인해야 한다.
오름차순 우선순위 큐를 활용하는 방법을 사용하였다.
Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.
끝 시간을 우선순위 큐로 관리하면 된다. 시작 시간순으로 배열을 확인하면서 끝 시간을 우선순위 큐에 Push 하면 되는데 만약 시작 시간이 우선순위 큐에 Top보다 크거나 같다면 같이 들을 수 있다는 뜻이므로 Pop해주면 된다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
priority_queue<int, vector<int>, greater<int>> pq;
vector<pair<int, int>> time;
cin >> N;
while (N--)
{
int s, e;
cin >> s >> e;
time.push_back({s, e});
}
sort(time.begin(), time.end());
pq.push(time[0].second);
for (int i = 1; i < time.size(); ++i)
{
if (pq.top() <= time[i].first)
{
pq.pop();
}
pq.push(time[i].second);
}
cout << pq.size();
return 0;
}풀이
오름차순 우선순위 큐를 선언해준다.
그 후 시간을 시작 시간순으로 정렬한 뒤 차례대로 끝 시간을 집어넣는다. 만약 시작 시간이 우선순위 큐에 끝 시간보다 크거나 같다면 이어서 수업을 할 수 있는 것이므로 pop 해준다. pq는 강의실의 개수이자 강의실에 마지막 시간을 저장해둔 곳이라고 생각해도 된다.
