[c++] 무지의 먹방 라이브

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> food_times, long long k) {
    int answer = 0;
    int len=food_times.size();
    vector<int> ft;
    long long Max=0;
    for(int i=0;i<len;i++){
        ft.push_back(food_times[i]);
        Max+=food_times[i];
    }
    if(Max<=k)
        return -1;
    sort(ft.begin(),ft.end());
    long long cnt=0;
    int pos=0;
    int depth=1;
    while(cnt<=k){
        cnt+=len;
        if(cnt>k){
            cnt-=len;
            break;
        }
        depth++;
        if(ft[pos]<depth){
            pos++;
            len--;
            while(ft[pos-1]==ft[pos]){
                pos++;
                len--;
            }     
        }
    }
    for(int i=0;i<food_times.size();i++){
        if(food_times[i]<depth)
            continue;
        cnt++;
        if(cnt==k+1){
            answer=i+1;
            break;
        }
    }
    return answer;
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=cpp

 

모든 음식을 먹기위해 전부 순회하는 경우 k가 long long 이므로 효율성 테스트를 통과못할 것이라고 예상했다.

정렬을 시킨후 일정 높이 이상의 범위 사이에서만 순회하면 food_times의 길이만큼 시간이 걸리므로 효율성 테스트 통과 가능!

 

처음엔 vector <pii> 형태로 음식의 번호 까지 ft에 저장하려고 했지만, k가 몇번째 depth에 존재하는지 알면 단순 순회해서 음식번호를 k+1번째에 도달하는 것으로 출력하면 정답이므로, 따로 음식 번호를 관리하지 않았다..