(2018)kakao blind recruitment > 무지의 먹방 라이브

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42891

정답률 : 정확성 42.08% / 효율성 5.52%

풀이

결국 효율성 부분을 잡아야하는 문제이다.

만약 정확성만 고려한다면 매 초마다 처리해주어 시간은 오래걸리지만 정답은 맞는 코드를

짤 수 있을것이다.

아무튼 맨 처음에 한 것은 vector<pair<int, int>> tmp(size) //size는 food_times의 크기

이것을 선언해 주어 food_times와 그 index를 넣어준 것이다

이후 이것을 food_times의 오름차순으로 정렬하였다.

만약 1 3 5 7 9 라고 정렬이 되었다 치면 

처음에는 1*5 -> 5초를 한번에 처리할 수 있고, 다음엔 (3-1)*4 -> 8초를 한번에 처리할 수 있다.

이런식으로 처리해주며 시간을 누적했을 때 만약 k보다 시간이 커지는 순간이 온다면

해당 사이클에 음식이 처리된 것 이므로 어떤 음식이 앞에있는지 골라낸다.

그래서 이 때 올려져있는 음식들에 대해 index순서대로 sorting을 다시 진행하였고

k에서 k보다 커지기 전의 누적시간을 뺀 후 나머지 연산을 통해 음식을 골라내었다.

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

using namespace std;

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	return p1.second < p2.second;
}
int solution(vector<int> food_times, long long k) {
	int size = food_times.size();
	vector<pair<int, int>> tmp(size);
	for (int i = 0; i < size; i++)
		tmp[i] = { food_times[i],i + 1 };
	sort(tmp.begin(), tmp.end());
	long long before = 0;
	long long sum = 0;
	for (int i = 0; i < size; i++)
	{
		before = sum;
		if ((i == 0) && ((size-i) * tmp[0].first <= k)) {
				sum = (size-i)*tmp[i].first;
				continue;
		}
		else if (i != 0) {
			sum += (tmp[i].first - tmp[i - 1].first) *(size - i);
			if (sum <= k) continue;
		}

		k -= before;
		sort(tmp.begin() + i, tmp.end(), cmp);
		int cnt = size - i;
		return tmp[i + (k%cnt)].second;
	}
	return -1;

}
int main()
{
	vector<int> food_times{3,1,2};
	cout << solution(food_times, 6);
}