26. Uva-1203 Argus //Priority Queue & 비교연산자의 특수화

우선 문제를 푸는데 사용한 자료구조인 PQ에 대해 알아보자. PQ는 최소한 다음 작업들이 지원되어야 하는 자료구조를 말한다. 우리는 뭘 해주는지만 알면 된다.

 

• 가장 높은 우선순위를 갖는 원소(최대 원소)를 Queue에서 꺼내는 작업 : ExtractMax()
• 새로운 원소 v를 Queue에 추가하는 작업: Insert(v)

또한, 이런 작업들은 Heap을 이용하여 구현할 시 lgN시간 안에 수행할 수 있다. C++ STL에서 priority_queue라는 이름으로 지원하고 있다. (PQ는 Heap이 아니다. PQ를 Heap을 이용해 구현할 수 있는 개념)

STL priority_queue에서 지원하는 작업은 다음과 같다.

(0) 정의: priority_queue<자료형, 구현체, 비교 연산자> ex) priority_queue<int,vector<int>,less<int> > PQ;

구현체는 쓰지 않아도 기본적으로 vector로 되어있다고 한다.

또한 비교 연산자는 기본적으로 less이고 이는 max가 제일 앞에 오는 PQ를 만든다. 반대로 만들고 싶으면 greater를 쓰면 된다.

(1) PQ.top()

(2) PQ.pop()

(3) PQ.push(element)

 

그럼 이제 문제를 보자.

 

문제

<그림1: 문제 설명>

 

Register QID interval 순으로 들어오는 input을 저장해서 시간 순서대로 QID를 출력하라는 것. QID는 interval에서 시작하고 interval마다 반복됨. 즉 첫 2004 process는 200, 400, 600...이렇게 실행되는 것.

만약 동일 시점에 여러 process가 있다면 QID가 작은놈부터 실행할 것. 따라서 자료가 정렬되어있어야 하니까 PQ구조를 이용했다.

코드는 다음과 같다.

 

#include<iostream>
#include<queue>
using namespace std;
struct ii {
	int first;	//QID
	int second;	//time(next start point)
	int period; //interval

};
struct cmp{
	bool operator()(ii in1, ii in2) {
		//first가 QID, second가 time임
		if (in1.second == in2.second) return (in1.first > in2.first);
		else return in1.second > in2.second;
	}
};
int main() {
	string input_query;
	int cur_time;
	priority_queue<ii,vector<ii>,cmp > Queries;
	int Q_num, interval, K;
	while (cin >> input_query) {
		if (input_query == "Register") {
			cin >> Q_num >> interval;
			Queries.push(ii{Q_num,interval,interval});
		}
		else {	//input of '#'
			break;
		}

	}
	//input 다 받아서 QandI_input 다 채움
	cin >> K;

	for (int i = 0; i < K; i++) {	//prototype of output
		cur_time = Queries.top().second+Queries.top().period;
		cout << Queries.top().first<<endl;
		Queries.push(ii{ Queries.top().first ,cur_time,Queries.top().period });
		Queries.pop();
	}
	return 0;
}

이때 PQ를 정의시 우리가 사용한 ii라는 구조체에 대한 비교연산자가 기본으로 제공되지 않기 때문에 다음과 같은 구조체를 제공하여야 한다.

struct cmp{
	bool operator()(ii in1, ii in2) {
		//first가 QID, second가 time임
		if (in1.second == in2.second) return (in1.first > in2.first);
		else return in1.second > in2.second;
	}
};

이 문법을 꼭 기억해놓자!