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

문제풀이

그냥 회전을 시키면 시간초과가 나는문제이다. 

인덱스와 food time을 포함한 구조체(food)를 만들어 정렬한뒤 food time이 낮은거 부터 삭제해나간다.

food time 이 낮은수는 그다음 높은 food time 에서 빼가며 계산해 주는걸 잊어서는 안된다. 왜냐하면 그만큼은 다 돌았기 때문에 이러한 점을 고려하여 돌다가 차이만큼 뺄 수없을때 모듈러 연산을 진행한다.

 

말이 너무 복잡하니 코드를 보면 이해가 쉬울거 같다. '

 

accumulate는 누적된 시간이라 생각하면되고

spend는 한번에 넘길 턴? 한번에 소비할 시간이라 보면된다. 

소스코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
typedef struct Food {
    int num;
    int times;
    Food() {}
    Food(int n, int t) {
        num = n;
        times = t;
    }
}Food;
using namespace std;
 
bool cmp_t(Food f1, Food f2) {
    return f1.times < f2.times;
}
bool cmp_n(Food f1, Food f2) {
    return f1.num < f2.num;
}
int same_cnt(vector<Food> ft) {
    int times = ft[0].times;
    for (int i = 1; i < ft.size(); i++) {
        if (times != ft[i].times)
            return i;
    }
    return ft.size();
}
 
 
int solution(vector<int> food_times, long long k) {
    int answer = 0;
    vector<Food> ft;
    for (int i = 1; i <=food_times.size(); i++) {
        ft.push_back(Food(i, food_times[i-1]));
    }
    sort(ft.begin(), ft.end(), cmp_t);
    int accumulate = 0;
    for (int i = 0,n=ft.size();i<ft.size();i++,n--) {
        long long spend = (long long)(ft[i].times - accumulate)*n;
        
        if (spend == 0) {
            //ft.erase(ft.begin());
            continue;
        }
        if (spend <= k) {
            k -= spend;
            accumulate = ft[i].times;
            //ft.erase(ft.begin());
        }
        else {
            k %= n;
            sort(ft.begin()+i, ft.end(), cmp_n);
            return ft[i+k].num;
        }
        
    }
    return -1;
}
 
int main() {
    vector<int> input = { 3,5,1,6,5,3 };
    printf("%d\n", solution(input, 20));
}
 

문제 링크 : www.programmers.co.kr/learn/courses/30/lessons/42891

프로그래머스