126. 무지의 먹방 라이브

프로그래머스

• 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.

• 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

• 회전판에 먹어야 할 N 개의 음식이 있다.

  • 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.

• 무지는 다음과 같은 방법으로 음식을 섭취한다.

  • 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.

  • 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.

  • 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.

    • 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.

• 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

• 무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.

  • 무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.

• 각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

• 제한사항

  • food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.

  • k 는 방송이 중단된 시간을 나타낸다.

  • 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

• 정확성 테스트 제한 사항

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

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

  • k는 1 이상 2,000,000 이하의 자연수이다.

• 효율성 테스트 제한 사항

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

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

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

입출력 예 #1

• 0~1초 동안에 1번 음식을 섭취한다. 남은 시간은 [2,1,2] 이다.
• 1~2초 동안 2번 음식을 섭취한다. 남은 시간은 [2,0,2] 이다.
• 2~3초 동안 3번 음식을 섭취한다. 남은 시간은 [2,0,1] 이다.
• 3~4초 동안 1번 음식을 섭취한다. 남은 시간은 [1,0,1] 이다.
• 4~5초 동안 (2번 음식은 다 먹었으므로) 3번 음식을 섭취한다. 남은 시간은 [1,0,0] 이다.
• 5초에서 네트워크 장애가 발생했다. 1번 음식을 섭취해야 할 때 중단되었으므로, 장애 복구 후에 1번 음식부터 다시 먹기 시작하면 된다.

1. 그리디 알고리즘

## 테스트 케이스 50%정도 통과


def solution(food_times, k):

    
    plus = 0
    for _ in range(k):
        rotate = plus % (len(food_times))
        #print('plus', plus)
        #print('rotate',rotate)
        if(food_times[rotate] == 0):
            plus += 1
            rotate = plus % (len(food_times))
            #print('change_rotate', rotate)
        food_times[rotate] -= 1
        plus += 1

        #print(food_times)
   
   

    if food_times[(rotate+1)%3] == 0:
        answer = -1
    else:
        answer = ((rotate+1) % 3) + 1
    return answer

#print(solution([3,1,2], 5))

정답

import heapq

def solution(food_times, k):
    # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1

    # 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i + 1))  

    sum_value = 0 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수

    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1 # 다 먹은 음식 제외
        previous = now # 이전 음식 시간 재설정

    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x: x[1]) # 음식의 번호 기준으로 정렬
    return result[(k - sum_value) % length][1]

• 모든 음식을 시간을 기준으로 정렬한 뒤에, 시간이 적게 걸리는 음식부터 제거해 나가는 방식을 이용하면 된다.

  • 이를 위해 우선순위 큐를 이용하여 구현할 수 있다.

• 3개의 음식이 있으며, K = 15 라고 해보자

  • 1번 음식: 8초 소요

  • 2번 음식: 6초 소요

  • 3번 음식: 4초 소요

  1) 초기 단계에서는 모든 음식을 우선순위 큐(최소 힙)에 삽입한다.

  • 마지막에 K초 후에 먹어야 할 음식의 번호를 출력해야 하므로 우선순위 큐에 삽입할 때 (음식 시간, 음식 번호)의 튜플 형태로 삽입한다.

    • 전체 남은 시간(K): 15초

    • 남은 음식: 3개

  2) 첫 단계에서는 가장 적게 걸리는 음식인 3번 음식을 뺀다.

  • 다만, 음식이 3개 남아 있기에 3(남은 음식의 개수) x 4(3번 음식을 먹는 시간) = 12를 빼야한다.

    • 즉 다 먹는 데 12초가 걸린다는 소리다.

  • 전체 남은 시간이 15초에서 3초로 줄게 된다.

    • 전체 남은 시간(K): 15초

    • 남은 음식: 2개

    • 먹은 음식들: (4, 3)

  3) 이번 단계에서는 2번 음식을 빼야 한다.

  • 전체 음식이 2개 남았으므로 2(남은 음식의 개수) x 2(2번 음식을 다 먹는 시간) = 4초가 된다.

  • 현재 남은 시간이 3초인데, 이는 4보다 작으므로 빼지 않도록 한다.

  • '다음으로 먹어야 할 음식 번호'를 찾아서 출력하면 된다.

    • 전체 남은 시간이 3초이므로, 4번째 음식의 번호를 출력하면 정답이다.

2. C++ 코드

#include <bits/stdc++.h>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int solution(vector<int> food_times, long long k) {
    // 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    long long summary = 0;
    for (int i = 0; i < food_times.size(); i++) {
        summary += food_times[i];
    }
    if (summary <= k) return -1;
    
    // 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    priority_queue<pair<int, int> > pq;
    for (int i = 0; i < food_times.size(); i++) {
        // (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        pq.push({-food_times[i], i + 1});
    }
    
    summary = 0; // 먹기 위해 사용한 시간
    long long previous = 0; // 직전에 다 먹은 음식 시간
    long long length = food_times.size(); // 남은 음식의 개수

    // summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while (summary + ((-pq.top().first - previous) * length) <= k) {
        int now = -pq.top().first;
        pq.pop();
        summary += (now - previous) * length;
        length -= 1; // 다 먹은 음식 제외
        previous = now; // 이전 음식 시간 재설정
    }

    // 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    vector<pair<int, int> > result;
    while (!pq.empty()) {
        int food_time = -pq.top().first;
        int num = pq.top().second;
        pq.pop();
        result.push_back({food_time, num});
    }
    sort(result.begin(), result.end(), compare); // 음식의 번호 기준으로 정렬
    return result[(k - summary) % length].second;
}

3. Java 코드

import java.util.*;

class Food implements Comparable<Food> {

    private int time;
    private int index;

    public Food(int time, int index) {
        this.time = time;
        this.index = index;
    }

    public int getTime() {
        return this.time;
    }

    public int getIndex() {
        return this.index;
    }

    // 시간이 짧은 것이 높은 우선순위를 가지도록 설정
    @Override
    public int compareTo(Food other) {
        return Integer.compare(this.time, other.time);
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        // 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
        long summary = 0;
        for (int i = 0; i < food_times.length; i++) {
            summary += food_times[i];
        }
        if (summary <= k) return -1;

        // 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
        PriorityQueue<Food> pq = new PriorityQueue<>();
        for (int i = 0; i < food_times.length; i++) {
            // (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
            pq.offer(new Food(food_times[i], i + 1));
        }

        summary = 0; // 먹기 위해 사용한 시간
        long previous = 0; // 직전에 다 먹은 음식 시간
        long length = food_times.length; // 남은 음식의 개수

        // summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
        while (summary + ((pq.peek().getTime() - previous) * length) <= k) {
            int now = pq.poll().getTime();
            summary += (now - previous) * length;
            length -= 1; // 다 먹은 음식 제외
            previous = now; // 이전 음식 시간 재설정
        }

        // 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
        ArrayList<Food> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }
        // 음식의 번호 기준으로 정렬
        Collections.sort(result, new Comparator<Food>() { 
            @Override
            public int compare(Food a, Food b) {
                return Integer.compare(a.getIndex(), b.getIndex());
            }
        });
        return result.get((int) ((k - summary) % length)).getIndex();
    }
}