75. 최대 수입 스케줄(priority_queue 응용문제) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Pay
{
	int pay, day;
	Pay(int x, int y) // 구조체 생성자
	{
		pay = x;
		day = y;
	}
	
	bool operator<(const Pay &x)const // 구조체 정렬기준을 연산자 오버로딩으로 구현
	{
		return day > x.day; // day = this.day , x.day = Pay x의 day
	}
};

int main()
{
	int n, d, m, j = 0, max = 0, answer = 0;
	scanf("%d", &n);
	
	vector<Pay> allPay;
	priority_queue<int> pQ;
	
	for(int i = 1; i <= n; i++)
	{
		scanf("%d %d", &m, &d);
		allPay.push_back(Pay(m, d));
		if(max < d) // 제일 긴 날짜 설정
			max = d;
	}
	sort(allPay.begin(), allPay.end());

	for(int i = max; i >= 1; i--) // 3일차부터
	{
		for(; j < allPay.size(); j++) // 매우 중요한 부분!! j를 계속해서 0으로 초기화하지 않는다
        // 잠시 break 되었다가 break된 지점부터 다시 시작하는 방식이다.
		{
			Pay a = allPay[j];
			if(a.day < i)
				break;
			pQ.push(a.pay);
		}
		
		if(!pQ.empty())
		{
			answer += pQ.top();
			pQ.pop();
		}
	}
	
	printf("%d", answer);
	return 0;
	
}

1. 이 문제에서는 여러 쌍의 변수를 갖는 구조체 struct 을 사용하였다. vector의 pair를 사용해도 되지만, 구조체에서는 연산자 오버로딩을 활용해서 구조체의 데이터를 내가 어떻게 구현하느냐에 따라서 정렬할 수 있다.

 

struct Pay
{
	int pay, day;
	Pay(int x, int y)
	{
		pay = x;
		day = y;
	}
	
	bool operator<(const Pay &x)const
	{
		return day > x.day;
	}
};

2. 연산자 오버로딩을 사용할 때는 operator<(Pay &x) 와 같은 형태로 사용한다. 이 멤버 함수의 매개변수는 구조체의 주소로 받는다.

• bool operator(const Pay &x) : 구조체 x에 의해서 원본을 임의로 변경 불
• bool operator(const Pay &x) const : 이 멤버 함수가 구조체 x의 멤버 변수를 임의로 변경 불가