카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++

https://www.welcomekakao.com/learn/courses/30/lessons/42891

정확성 테스트는, 그냥 조건대로 시뮬레이션을 돌리면 통과할 수 있지만, 효율성 테스트는 통과할 수 없다.

k의 범위가 매우 큰데, 나이브하게 풀면 k번 탐색해야하기 때문이다.

k번 탐색할 게 아니라, 최대로 음식의 개수만큼만 탐색하도록 구현할 수 있다.

음식을 먹는 데 소요되는 시간을 오름차순으로 정렬하고, 

(현 시점에서 가장 적은 시간이 소요되는 음식의 시간 * 남아있는 음식의 수)만큼의 시간을 한 번에 감소시킬 수 있다.

당연히 k도 갱신되어야 하고, 위에 계산한 시간이 k보다 작아야 가능하다.

저 시간이 k보다 크다면, 음식별 소요 시간으로 정렬해 두었던 것을, 다시 본래의 인덱스로 돌려준다. 이것 때문에 초반에 pair에 음식별 소요시간과 그 음식의 번호를 함께 저장하는 것이다.

이제는 나머지 연산을 활용해서, 먹어야할 음식을 찾아주면 된다.

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
bool cmp(pii a, pii b) {
    return a.second < b.second;
}
int solution(vector<int> ft, long long k) {
    vector<pii> foods;
    for (int i = 0; i < ft.size(); i++) 
        foods.push_back({ ft[i], i + 1 }); //음식의 번호는 1부터
    
    sort(foods.begin(), foods.end());
    int remain = foods.size();
    ll spend, preTime = 0; //spend = 현 시점에서 한번에 지울 수 있는 시간, pretime = 이전에 봤던 음식의 소요 시간
    for (vector<pii>::iterator itr = foods.begin(); itr != foods.end(); itr++, remain--) {
        spend = (itr->first-preTime) * remain;
        preTime = itr->first;
        if (spend == 0) continue;
        else if (spend <= k) { //한번에 spend만큼 지울 수 있으면
            k -= spend;
        }
        else { //한번에 먹을 수 있는 양보다 k가 작으면
            sort(itr, foods.end(), cmp);//다시 음식들 원위치로 정렬
            k %= remain;
            return (itr + k)->second;
        }
    }
    return -1; //먹을 수 있는 게 없어서, spend가 k보다 커진적 없이, 계속 0이라 스킵된 경우
}
int main(void) {
    vector<int> v;
    v = { 3,5,1,6,5,3 };
    int k = 20;
    solution(v, 20);
    return 0;
}