프로그래머스 문제 - 무지의 먹방 라이브

프로그래머스 무지의 먹방 라이브 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

회전판에 먹어야 할 음식 N개가 있습니다.
음식은 1번부터 N번까지 순서대로 번호가 붙어있으며 각 음식을 다 먹기까지 걸리는 시간이 존재하며, 1번부터 음식을 먹기 시작합니다.
음식을 1초동안 먹은 후 남은 음식은 두고 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 먹습니다.
먹방을 시작한지 K초 후에 정전이 일어나게 되고 복구된 후에 먹어야 할 음식을 return해야 합니다.

문제 풀이

음식을 순환하며 먹을 때 K초 이후에 먹는 음식을 찾아야합니다.
음식을 다 먹을 시에는 음식을 순환할 때 넘어가야 하기 때문에 다 먹은 음식과 남은 음식을 알고 있어야 합니다.

일단 하나씩 순환하며 음식을 찾기에는 K값이 정말 크기 때문에 시간초과가 생기니 다른 방법을 찾아야합니다.
1초씩 모든 음식은 순서대로 먹기 때문에 음식을 다 먹기까지 걸리는 시간이 적은 음식부터 사라지게 됩니다.
즉 음식들 중 제일 걸리는 시간이 적은 음식의 시간만큼 순환하며 먹으면 1초씩 확인하지 않아도 한 개 이상의 음식을 다 먹을 때까지의 시간을 계산할 수 있습니다.

예시로 [3, 1, 2]원소를 가진 food_times라는 배열이 주어지고 k=5라면,
오름차순으로 정렬하게 되면 [1, 2, 3]이 됩니다.
food_times[0]의 음식을 다 먹을 만큼 순환하며 진행되었을 때 k값보다 더 적게 걸린다면 정전이 되기 전에 food_times[0]의 시간을 가진 음식들을 먹을 수 있다는 뜻이 됩니다.
단 순환한 횟수와 같은 음식이 나왔을 때는 이미 먹어서 없는 음식이므로 제외시키고 게산을 진행해야 합니다.
이런식으로 계산을 진행하면 어떤 음식을 다 먹기까지 걸리는 시간 내에 정전이 되는지 알 수 있게 됩니다.

while(sum+foodCount*(foods[index] - prevfood) <= k)
{   
    if(foods[index] - prevfood > 0)
    {
        sum += foodCount*(foods[index] - prevfood);
        prevfood = foods[index];
    }
    foodCount--;
    index++;
    if(index == foods.size())
    {
        return -1;
    }
}

이후 찾아낸 음식을 먹기 전에 정전이 되므로 남은 음식의 양 > 정전이 되기까지 남은 시간이 되도록 시간을 진행시킨 이후
정전이 끝나고 먹을 음식을 찾아주면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(vector<int> food_times, long long k) {
    int answer = 0;
    vector<int> foods = food_times;
    int foodCount = food_times.size();
    
    //오름차순 정렬
    sort(foods.begin(), foods.end());
    
    long long sum = 0;
    long long prevfood = 0;
    int index = 0;
    while(sum+foodCount*(foods[index] - prevfood) <= k)
    {
        if(foods[index] - prevfood > 0)
        {
            sum += foodCount*(foods[index] - prevfood);
            prevfood = foods[index];
        }
        foodCount--;
        index++;
        if(index == foods.size())
        {
            return -1;
        }
    }
    
    int cur = foods[index];
    while(k-sum >= foodCount)
    {
        sum += foodCount;
    }
    index = 0;
    while(sum != k+1)
    {
        if(food_times[index] - cur >= 0)
        {
            sum++;
        }
        index++;
    }
    answer = index;
    
    return answer;
}

출저

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