[카카오 2019] 코딩테스트 - 무지의 먹방 라이브

문제출처

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

효율성 테스트가 있는 문제이다. 

전체 탐색을 하면 효율성 테스트에서 통과하지 못한다. idea는 정렬을 통해 가장 작은 값의 시간을 한번에 빼는 방법을 사용하였다.

소스코드

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool comp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}
 
int solution(vector<int> food_times, long long k) {
    vector<pair<int, int>> food;
    int size = food_times.size();
    for(int i=0; i<size; i++)
        food.push_back(make_pair(food_times.at(i), i+1));
    
    sort(food.begin(), food.end());
    
    int time=0;
    for(vector<pair<int, int>>::iterator it=food.begin(); it!=food.end(); it++, size--) {
        long long leadTime = (long long)(it->first - time) * size;
        if(leadTime == 0)
            continue;
        
        if(leadTime <= k) {
            k-=leadTime;
            time=it->first;
        } else {
            k%=size;
            sort(it, food.end(), comp);
            return (it+k)->second;
        }       
    }
    return -1;
}