[SW Expert Academy] D2 1859. 백만 장자 프로젝트(c++)

시간제한이랑 타입때문에 좀 헤맸다..

set을 사용했는데, max_element를 사용해도 되지 않을까 하는 생각도 했다.

하지만 전에 계속 도는 프로그램을 만들었었는데 시간초과가 났고, max_element도 O(n)이라는 말을 보고 사용하지 않았다. 다른사람 코드 보면 사용해도 될거같기도하고?

 

#include <iostream>
#include <set>
#include <map>
#include <vector>

using namespace std;

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int day, price;
		cin >> day;
		vector<int> days;
		map<int, int> price_cnt;
		for (int j = 0; j < day; j++) {
			cin >> price;
			price_cnt[price] += 1;
			days.push_back(price);
		}

		set<int> prices(days.begin(), days.end());
		long long result = 0;
		for (auto d : days) {
			price_cnt[d] -= 1;

			result += (*prices.rbegin() - d);
			if (price_cnt[d] == 0) prices.erase(d);
		}
		cout << "#" << i + 1 << " " << result << '\n';
	}
	
	return 0;
}

---

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

728x90

---

[접근 1]

우선 전부 돌면서 가격들을 vector인 days에 넣었고, 각 가격 숫자들을 count 했다(price_cnt).

vector<int> days;
map<int, int> price_cnt;
for (int j = 0; j < day; j++) {
    cin >> price;
    price_cnt[price] += 1;
    days.push_back(price);
}

---

[접근 2]

가격들을 넣은 days를 복사해서 prices라는 set을 만들었고,

하루하루 돌면서 해당하는 가격의 개수는 1개 줄여주고, result에는 set의 맨 뒤 원소 즉, 제일 큰 원소에 당일 가격을 빼서 더해준다.

만약 해당 가격의 price_cnt가 0이된다면 set에서 해당 가격을 제외시켜 이후 최대값을 구하는데 차질이 없게 한다.

set<int> prices(days.begin(), days.end());
long long result = 0;
for (auto d : days) {
    price_cnt[d] -= 1;

    result += (*prices.rbegin() - d);
    if (price_cnt[d] == 0) prices.erase(d);
}