[백준 22867] 종점 (C++)

문제 링크: https://www.acmicpc.net/problem/22867

22867번: 종점

1. 주의할 점

- 정렬 방법을 잘 수립한다

- 우선순위 큐를 사용한다

- 초기에 구상했던 정렬에 대한 반례는 아래에 있습니다 (PQ 1개만 이용)

#TC 1

3
00:00:00.000 00:00:00.002
00:00:00.000 00:00:00.010
00:00:00.002 00:00:00.010
AC: 2

 

#TC 2

6
00:00:00.000 00:00:00.002
00:00:00.000 00:00:00.010
00:00:00.001 00:00:00.008
00:00:00.004 00:00:00.006
00:00:00.005 00:00:00.008
00:00:00.007 00:00:00.009

AC: 4

 

2. 구현

- HH:MM:SS.sss로 입력되는 수를 calToMsec() 함수를 통해 전부 ms로 계산한 값을 구조체에 담는다. 이때, 구조체에는 들어온 시간, 나가는 시간이 ms 단위로 환산되어있다

- 버스에 대한 정보를 종점에 들어오는 시간에 대한 오름차순, 같다면 나가는 시간에 대한 오름차순으로 정렬하는 우선순위 큐 PQ에 담는다

- onStation 우선순위 큐는 나가는 시간에 대한 오름차순, 같다면 들어오는 시간에 대한 내림차순으로 정렬한다

- PQ에서 정보를 1개씩 빼면서 아래 과정을 PQ가 empty가 될때까지 진행한다

- 현재 onStation의 Top에 있는 원소의 나가는 시간보다 작다면 onStation에 추가하고 answer++를 수행한다

- 반대로 onStation의 Top에 있는 원소의 나가는 시간 이상이면 onStation에 대한 While문을 통해 현재 버스와 겹치지 않는 버스를 빼낸다. 이후, onStation에 현재 버스에 대한 정보를 담는다

 

#include <iostream>
#include <string>
#include <stdlib.h>
#include <queue>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
	int comeHms, leaveHms;
};
struct cmp {
	bool operator()(info &a, info &b) {
		if (a.comeHms == b.comeHms) {
			return a.leaveHms > b.leaveHms;
		}
		return a.comeHms > b.comeHms;
	}
};
struct cmp2 {
	bool operator()(info &a, info &b) {
		if (a.leaveHms == b.leaveHms) {
			return a.comeHms < b.comeHms;
		}
		return a.leaveHms > b.leaveHms;
	}
};

int calToMsec(string ss) {
	int hour = stoi(ss.substr(0, 2));
	int min = stoi(ss.substr(3, 2));
	int sec = stoi(ss.substr(6, 2));
	int msec = stoi(ss.substr(9));
	return (3600000 * hour) + (60000 * min) + (sec * 1000) + msec;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, answer = 1, result = 1;
	string come, leave;
	cin >> num;
	priority_queue<info, vector<info>, cmp> pq;
	priority_queue<info, vector<info>, cmp2> onStation;

	for (int i = 0; i < num; i++) {
		cin >> come >> leave;
		pq.push({ calToMsec(come),calToMsec(leave) });
	}
	onStation.push({ pq.top().comeHms, pq.top().leaveHms });
	pq.pop();
	while (!pq.empty()) {
		int left = pq.top().comeHms;
		int right = pq.top().leaveHms;
		if (onStation.top().leaveHms > left) {
			onStation.push({ left,right });
			answer++;
		}
		else {
			while (!onStation.empty()) {
				int r = onStation.top().leaveHms;
				if (r <= left) {
					onStation.pop();
					answer--;
				}
				else 
					break;
			}
			onStation.push({ left,right });
			answer++;
		}
		result = max(result, answer);
		pq.pop();
	}
	cout << result;
	return 0;
}