# 42891. 무지의 먹방 라이브

관련 알고리즘 : Greedy, priority queue

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

코딩테스트 연습 - 무지의 먹방 라이브

 

<기본 제공 코드>

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> food_times, long long k) {
    int answer = 0;
    return answer;
}

 

효율성 테스트 제한 사항

food_times 의 길이는 1 이상 200,000 이하이다.

food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.

k는 1 이상 2 x 10^13 이하의 자연수이다.

 

---

풀이과정

 

완전탐색(Brute-force)을 이용하여도 구할 수 있지만 시간 때문에 효율성 테스트에 통과하지 못했다. 그래서 완전탐색은 사용이 불가능하다. ( 시간초과 + 비효율적)

따라서 K초가 지난 후 먹게 되는 음식의 번호를 빠르게 계산하기 위해서 그리디 알고리즘과 우선순위 큐를 사용하여 문제를 해결하였다.

 

문제에서 제공한 예시로는 해당 과정을 생각하기가 어려워 하나 예시를 만들어 시도하였다.

 

K =  14

#1 : 5

#2 : 8

#3 : 4

#4 : 2

(각 음식 번호와 음식 먹는데 소요되는 시간)

 

우선순위 큐에 의해 해당 음식들을 오름차순으로 정렬하면 

 

#4 : 2

#3 : 4

#1 : 5

#2 : 8

 

순이며, 그리디 알고리즘에 의해 먹는 데 시간이 가장 적게 소요되는 4번 음식을 다 먹는데 걸리는 시간은

2(4번음식을 다 먹는데 소요되는 시간) x 4 (남아있는 음식 개수)

해당 K초를 다 소모할 때까지 위 작업 (남아있는 음식 중 먹는 데 소요되는 시간이 가장 적은 음식을 다 먹는데 소요되는 시간) x (남아있는 음식 개수) 을 반복하게 된다.

 

위 예시에서 4번 음식을 다 먹는데 2x4=8초를 소요하였으므로, K=14-8=6 이 된 시점에서

남아있는 음식들은 각각 다 먹는데

 

k = 6

#4 : 2-2=0

#3 : 4-2=2

#1 : 5-2=3

#2 : 8-2=6

 

초가 소요된다. 이후 3번 음식에 대해 해당 작업을 반복하면 3번 음식을 다 먹는데

2 (남아있는 3번 음식 다 먹는데 소요되는 시간) x 3 (남아있는 음식 개수) = 6초가 소요되므로

남아있는 6초를 다 써서 K=0 이 된다.

 

K = 0

#4 : 0

#3 : 2-2=0

#1 : 3-2=1

#2 : 6-2=4

 

이 때, 남아있는 음식은 1번과 2번이며 각각 다 먹는데 1, 4초가 소요된다.

회전판은 오름차순으로 음식을 무지에게 갖다주므로, 남아있는 음식의 번호 순으로 오름차순 정렬하여 가장 작은 번호를 가진 음식이 해당 문제의 답이 된다.

---

해결 코드 - C++

1. priority queue 이용, pair<번호, 시간> 시간 오름차순 정렬 후

k - (남아있는 음식 중 다 먹는데 소요시간 제일 작은것) x (남아있는 음식 개수

 

   2. k=0일 때, 다시 pair를 번호 오름차순 정렬 ( 이 때, pair의 시간 != 0인 것만 )

   3. 그 중 제일 앞에 있는 음식의 번호 출력

 

이를 코드로 나타내면 다음과 같다.

// 프로그래머스 42891.무지의 먹방 라이브

#include <string>
#include <vector>
#include <algorithm> 
#include <queue>

using namespace std;

int solution(vector<int> food_times, long long k) 
{
    long long sum = 0; // 전체 음식 먹는데 걸리는 시간
    for(int i=0; i<food_times.size(); i++)
    {
        sum += food_times[i];
    }
    if(sum <= k) //  전체 음식을 먹는 시간보다 k가 더 클때 섭취해야 할 음식 없으므로
        return -1; // -1 반환

    priority_queue<pair<int,int>> food; // <시간, 번호> 우선순위 큐

    for(int i =0; i<food_times.size(); i++)
    {
        food.push({-food_times[i], i+1}); //  음식 시간 오름차순 삽입
    }

    long long prev = 0; // 직전 식사시간
    while((-food.top().first - prev) * food.size() <= k)
    {
        k -= (-food.top().first - prev) * food.size(); // {남은 전체시간 - (남은 음식 중 섭취시간이 가장 작은것) * (남은 음식 개수)} 로 전체시간 초기화
        prev = -food.top().first;
        food.pop(); // 다 먹은 음식 pop
    }

    vector<pair<int,int>> leftover; // K초 초과 후 남은 음식 넣을 벡터
    while(!food.empty())
    {
        leftover.push_back(make_pair(food.top().second, -food.top().first)); // <번호, 시간> 벡터
        food.pop(); // leftover에 넣은 벡터 pop
    }

    sort(leftover.begin(), leftover.end()); // 음식 번호기준 정렬
    return leftover[k % leftover.size()].first; // 몇 번 음식부터 먹으면 되는지 계산 후 반환 
}

 

효율성 검사 결과 모두 통과하였고, 18점의 가산점을 얻었다.