문제

카카오 프로그래머스

풀이

후,,,, 문제를 푸는데 답을 보고 풀면 안되는데ㅠㅠ 아직도 실력이 안되긴 하나보다.
이번 문제를 통해 알게된 것은 우선순위 큐(priority_queue)이다.
일반적인 큐는 FIFO의 기능을 가지는데, 우선순위 큐는 프로그래머의 판단에 따라 우선순위를 두는 것이다.
이 문제를 풀 때 큐에 pair구조를 쓰는데(각 음식을 먹는 시간과 인덱스), default 우선순위는 max heap이라 큰 값부터 정렬을 해준다(pair의 first를 기준).
비교 연산자는 두가지만 알면 된다. less와 greater이 있는데 less는 내림차순, greater은 오름차순 정렬이다. 이를 사용하려면 functional 라이브러리를 include 해주어야 한다.
이 문제에서는 음식먹는 시간이 짧은 순서대로 정렬을 해야 하므로 오름차순으로 정렬을 해주었다. 구글링을 하는데 신박하 방법도 있었는데, default 연산자로 push해주는데 foot_time에 음수를 넣어서 내림차순 정렬을 해주고 후에 계산할 때 다시 -를 붙이는 것이다.

#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;

struct compare {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.first < b.first;
	}
};

int solution(vector<int> food_times, long long k) {
	ll sum = 0, before = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pfood_times;

	for (int i = 0; i < food_times.size(); i++) {
		sum += food_times[i];
		pfood_times.push(make_pair(food_times[i], (i + 1)));
	}

	if (sum <= k)
		return -1;

	while ((pfood_times.top().first - before) * pfood_times.size() <= k) {
    		if (pfood_times.size() == 1)
			return (pfood_times.top().first);
		k -= ((pfood_times.top().first - before) * pfood_times.size());
		before = pfood_times.top().first;
		pfood_times.pop();
	}
	vector<pair<int, int>> time;

	while (!pfood_times.empty()) {
		time.push_back(make_pair(pfood_times.top().second, pfood_times.top().first));
		pfood_times.pop();
	}

	sort(time.begin(), time.end());

	return time[k % time.size()].first;
}

int main()
{
	vector<int> v = { 3,1,2 };
	int n = solution(v, 5);
	cout << n;
}