무지의 먹방 라이브
문제 해석
K초까지 음식을 먹고 난 후, 다음 먹을 음식의 번호를 구하는 문제입니다.
회전판에 N개의 음식이 있고, 1번부터 차례대로 음식을 1초동안 먹습니다.
이 행위를 K초간 반복하면 됩니다.
설계(X)
효율성을 고려해서 아이디어를 생각해보았는데 아쉽게도 설계가 되지 않아서 카카오 해설지를 참조하였습니다.
K의 범위가 크므로 K를 1씩 줄여가면서 탐색할 수 없습니다.
먼저, 음식들을 시간 오름차순으로 정렬합니다.
이후에 한 사이클을 돌 때 마다 (T[i]-T[i-1])x(남은 음식 수)의 시간이 소모가 되는 것을 착안하여 K가 음수가 되기 전까지 감소시켜주는 것을 반복합니다.
그 후, 남은 K%(남은 음식 개수)가 0이 되는 음식 번호를 출력하면 됩니다.
음식이 남아있는지 체크하기 위해서 finished배열을 사용하여 다 먹은 음식의 번호를 체크해줍니다.
구현(X)
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> food_times, long long k) {
int n = food_times.size();
vector<bool> finished(n, false);
vector<pair<int, int> > tmp_v(n);
for (int i = 0; i < n; i++) {
tmp_v[i] = { food_times[i],i };
}
sort(tmp_v.begin(), tmp_v.end());
int idx;
for (idx = 0; idx < n; idx++) {
if (idx == 0) {
if (k < (long long)tmp_v[idx].first*n) break;
k -= (long long)tmp_v[idx].first*n;
}
else {
if (k < (long long)((tmp_v[idx].first-tmp_v[idx - 1].first) * (n - idx))) break;
k -= (long long)((tmp_v[idx].first-tmp_v[idx - 1].first) * (n - idx));
}
finished[tmp_v[idx].second] = true;
}
if (idx == n) return -1;
k %= (n - idx);
k++;
for (int i = 0; i < n; i++) {
if (finished[i]) continue;
k--;
if (k == 0) return i+1;
}
}
디버깅
제출결과
마무리
효율성을 만족하기 위해서 색다른 아이디어가 필요했던 문제입니다. 오래 전에 풀이를 해봤음에도 불구하고, 아이디어를 생각해내지 못했습니다. 유연한 사고를 더욱 기르기 위해서 다양한 문제들을 풀어봐야할 것 같습니다.