2019 KAKAO BLIND RECRUITMENT - 무지의 먹방 라이브

모든 문제는 C++로 구현되어 있습니다.

 

이 문제를 풀기 위해, 각 음식을 다 먹는 시간을 기준으로 구간을 나눠볼 수 있다. 아래와 같은 food_times 배열이 주어졌다고 가정해보자.

[10, 15, 4, 7]

가장 먼저 다 먹게되는 음식은 세 번째 음식으로, 다 먹는데에 4 X 4 = 16초가 걸린다.

두번째로 다 먹게 되는 음식은 네 번째 음식으로, 다 먹는데에 16 + (7-4) X 3 = 25초가 걸린다.

세번째로 다 먹게 되는 음식은 첫 번째 음식으로, 다 먹는데에 25 + (10-7) X 2 = 31초가 걸린다.

마지막으로 남는 음식은 두 번째 음식으로, 다 먹는데에 31 + (15-10) X 1 = 36초가 걸린다.

 

이런 식으로 구간을 나누면 K초 시점에서 몇개의 음식이 남았는지 확인할 수 있다. 그러면 K초에서 바로 이전의 음식을 다먹은 시점의 시간을 뺀 뒤, 이를 남은 음식의 갯수로 나눴을 때 나머지를 구하면 K초 시점에서 먹은 음식의 번호를 알 수 있다. 구간을 구하기 위해서는 새로운 배열을 생성해 내용을 복사한 뒤, 한 번 정렬해서 계산을 수행해야 한다. 계산식은 다음과 같다.

 

        // border : 구간값을 저장하는 배열
        // foodNum : food_times 배열의 길이  
        // tmp : food_times를 복사한 배열
        
	    for (i = 1; i < tmp.size(); i++) {
			border.push_back(border[i - 1] + (foodNum - i) * (tmp[i] - tmp[i - 1]));
		}

 

 

이 번호는 이미 다 먹은 음식의 번호를 고려하지 않고 매긴 번호이므로, 다시 food_times 배열을 순회하며 K초 시점에서 다 먹는데 걸리는 시간이 테이블 회전 수보다 작은 음식을 빼고 번호를 다시 매겨줘야 한다.

 

말로 설명하면 이해하기 어려울 수 있으니, 예시를 들어 확인해보자.

 

 

나누는 수에서 1을 빼준 것은 그대로 계산할 경우 첫 번째 음식의 나머지가 1이고 마지막 음식의 나머지가 0이 되므로, 1을 빼줘서 첫번째 음식의 나머지가 0, 마지막 음식의 나머지가 n-1이 되도록 했다. 

 

번호를 구한 뒤에는 다음에 먹어야할 음식을 구하기 위해 구한 번호에 1을 더한 뒤, 남은 음식의 수로 나눈 나머지를 구해준다. 이 값을 food_times를 순회하며 1씩 빼준다. 이때, food_times의 원소가 K초 시점에서 테이블이 회전한 횟수 이하라면 빼지 않고 그냥 넘어간다. 0이 되는 시점의 배열 인덱스가 우리가 최종적으로 구해야 할 음식의 번호이다. 

 

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

using namespace std;

typedef long long ll; //2019 KAKAO BLIND RECRUITMENT - 무지의 먹방 라이브

int solution(vector<int> food_times, ll k) {
	int answer = 0;
	ll sum = 0;
	for (auto time : food_times) {
		sum += time;
	}

	if (sum <= k) answer = -1;
	else {
		int i, foodNum = food_times.size();

		//1. 각각의 음식을 다 먹는데 걸리는 시간을 차례대로 기록함.
		vector<ll> border;
		vector<int> tmp = food_times;
		sort(tmp.begin(), tmp.end());
		border.push_back(foodNum * tmp[0]);

		for (i = 1; i < tmp.size(); i++) {
			border.push_back(border[i - 1] + (foodNum - i) * (tmp[i] - tmp[i - 1]));
		}

		//2. k초 동안 먹고 남아있는 음식 수, 테이블 회전 수, 그리고 찾는 음식의 번호를 구한다.
		//   여기서 구한 번호는 다 먹은 음식을 생각하지 않고 매긴것이므로, 다시 food_items 배열을 순회하며
		//   테이블 회전 수 이하인 음식들을 걸러내고 번호를 다시 매기면 최종 답을 구할 수 있다.
		ll rotateNum = 0, eatenFoodNum = 0, last = 0, findNum = -1;
		for (i = 0; i < border.size(); i++) {
			if (k > border[i]) {
				eatenFoodNum++;
				last = border[i];
				rotateNum = tmp[i];
			}
			else break;
		}

		ll div = (foodNum - eatenFoodNum);
		findNum = (k - last - 1) % div;
		findNum = (findNum + 1) % div;

		//3. 다 먹은 음식들은 걸러내고 다시 번호를 매겨 최종 답을 찾는다.
		for (i = 0; i < food_times.size(); i++) {
			if (food_times[i] <= rotateNum) continue;
			if (findNum == 0) {
				answer = i + 1;
				break;
			}
			findNum--;
		}
	}
	return answer;
}