75. 최대 수입 스케쥴(priority queue greedy: 구조체와 Vector를 이용한 정렬)

나의정답1. 최대힙 이용안함.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

struct money {
	int m, d;
	money(int m, int d) : m(m), d(d) {	}
	
	bool operator<(const money& com) const {
		if (d != com.d) return d > com.d;
		if (m != com.m) return m > com.m;	
		
	}
};

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	int n, m, d, res = 0, maxDate = -1, maxMoney = 0, idx;
	bool calc;
	vector<money> v;

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &m, &d);
		v.push_back(money(m, d));
		if (d > maxDate) maxDate = d;
	}

	for (int i = maxDate; i >= 1; i--) {
		//sort(v.begin(), v.end());
		maxMoney = 0;
		calc = false;
		for (int j = 0; j < n; j++) {
			if (v[j].d < i) continue;
			calc = true;

			if (maxMoney <= v[j].m) {
				maxMoney = v[j].m;
				idx = j;
			}
		}
		if (calc) {
			v[idx].d = -1;
			res += v[idx].m;
		}
	}

	printf("%d", res);

	return 0;
}

 

나의정답2. 최대힙 이용

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

struct money {
	int m, d;
	money(int m, int d) : m(m), d(d) {	}
	
	bool operator<(const money& com) const {
		if (d != com.d) return d > com.d;
		if (m != com.m) return m > com.m;	
	}
};

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	int n, m, d, res = 0, maxDate = -1;
	priority_queue<int> pq;
	vector<money> v;

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &m, &d);
		v.push_back(money(m, d));
		if (d > maxDate) maxDate = d;
	}

	for (int i = maxDate; i >= 1; i--) {
		for (int j = 0; j < n; j++) {
			if (v[j].d == i) {
				pq.push(v[j].m);
			}
		}
		if (!pq.empty()) {
			res += pq.top();
			pq.pop();
		}
	}

	printf("%d", res);
	return 0;
}