[2019 카카오] 무지의 먹방 라이브

https://programmers.co.kr/learn/courses/30/lessons/42891

프로그래머스

(무지는 왜 음식 하나를 100,000,000초동안 먹는가.. 무지는 왜 먹방을 20,000,000,000,000초동안 찍는가..)

 

쉽게 말해 k초가 지난 후 몇번째 음식을 먹을 차례인지를 묻는 문제

효율성테스트까지 통과하려면 규칙을 잘 찾아서 코딩해야 한다.

 

키 포인트는 회전판이 한 번 돌면 다시 제자리로 돌아오므로

이렇게 한 번 돌아서 다시 제자리로 오는 시간들을 k에서 모두 뺀 후

남은 k를 가지고 턴을 계산하는 것이다.

 

음식이 줄어듦에 따라 회전판을 한 번 도는시간이 줄어드는데

이 회전판을 한 번 도는 시간별로 몇 바퀴를 도는지 계산해서 k에서 빼주는 방식으로 구하면 된다.

 

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

using namespace std;

int solution(vector<int> food_times, long long k) {
	int answer = 0;
	int item = food_times.size();
	
	vector<int> sorted;
	sorted.assign(food_times.begin(), food_times.end());
	sort(sorted.begin(), sorted.end());

	int curr = -1;
	for (int i = 0; i < item; i++) {
		int x;
		if (i == 0) x = sorted[i];
		else x = sorted[i] - sorted[i - 1];

		long long add = (long long)x * (item - i);
		k -= add;

		if (k < 0) {
			k += add;
			k %= (item - i);
			curr = sorted[i];
			break;
		}
	}

	if (curr == -1) return -1;

	for (int i = 0; i < item; i++) {
		if (food_times[i] < curr) continue;

		if (k == 0) {
			answer = i;
			break;
		}
		k--;
	}

	answer++;

	return answer;
}