[2019 Kakao Blind] 무지의 먹방 라이브

이 문제는 예전에 파이썬으로 시도했으나 못풀었다...
그래서 그냥 넘어갔었는데 이번에는 도전을 했다.
하지만 역시나 실패... 후 왤케 몬하지!? :)
그래도 이번에는 정확성 테스트는 모두 맞았다.
하지만 효율성 테스트 0점.

내가 짠 소스 코드

내 소스는 아래와 같다.

import java.util.Arrays;

class Solution {
    public static void main(String[] args) {
        int[] foodTimes = {1, 1, 1, 1};
        long k = 4;
//        int[] foodTimes = {4, 2, 3, 6, 7, 1, 5, 8};
//        long k = 16;
        Solution sol = new Solution();
        System.out.println(sol.solution(foodTimes, k));
    }
    private boolean zeroCheck(int[] foodTimes) {
        if (Arrays.stream(foodTimes).sum() == 0) {
            return true;
        }
        return false;
    }
    public int solution(int[] foodTimes, long k) {
        int index = 0;
        while (k >= 0) {
            index = index % foodTimes.length;
            if (foodTimes[index] == 0) {
                if (zeroCheck(foodTimes)) {
                    return -1;
                }
                index += 1;
                continue;
            }
            foodTimes[index] -= 1;
            index += 1;
            k -= 1;
        }
        return index;
    }
}

열심히 공책에 알고리즘을 써가면서 짰다...
food_time이 0이면 index를 하나 넘겨야 하기 때문에 index 변수를 따로 두어 구현하였고,
섭취할 음식이 없을 때를 체크하기 위해 zeroCheck 메소드를 구현하였다.
하지만 결과는 실패!

그럼 다른 사람 풀이를 통해 내 자신을 되돌아보자...

남이 짠 소스 코드

package 이것이코딩테스트다.greedy.무지의_먹방_라이브;

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 time;
    }

    public int getIndex() {
        return index;
    }

    @Override
    public int compareTo(Food other) {
        return Integer.compare(this.time, other.time);
    }
}

public class Solution {
    public static void main(String[] args) {
        int[] foodTimes = {3, 1, 2};
        int k = 5;
        Solution sol = new Solution();
        System.out.println(sol.solution(foodTimes, k));
    }

    public int solution(int[] food_times, long k) {
        long summary = 0;
        for (int i = 0; i < food_times.length; i++) {
            summary += food_times[i];
        }
        if (summary <= k) {
            return -1;
        }

        PriorityQueue<Food> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < food_times.length; i++) {
            priorityQueue.offer(new Food(food_times[i], i + 1));
        }

        summary = 0;
        long previous = 0;
        long length = food_times.length;

        while (summary + ((priorityQueue.peek().getTime() - previous) * length) <= k) {
            int now = priorityQueue.poll().getTime();

            summary += (now - previous) * length;
            length -= 1;
            previous = now;
        }

        List<Food> result = new ArrayList<>();
        while (!priorityQueue.isEmpty()) {
            result.add(priorityQueue.poll());
        }

        Collections.sort(result, new Comparator<Food>() {
            @Override
            public int compare(Food o1, Food o2) {
                return Integer.compare(o1.getIndex(), o2.getIndex());
            }
        });

        return result.get((int) ((k - summary) % length)).getIndex();
    }
}

매우 길다.
하지만 이걸 이해해야 다음 단계로 넘어갈 수 있다.
하나씩 살펴보자.

코드 리뷰

기본 원리는 이렇다.

[3, 1, 2]이 있으면 순서대로 인덱스를 부여한다.
우선순위 큐를 사용하여 가장 시간이 적게 걸리는 것을 먼저 섭취한다.

[3, 1, 2] 중에서 시간이 가장 적게 걸리는 것은 1이므로 food_times 전체 길이 만큼 곱해주고 k에서 뺀다. k = 5이기 때문에 5 - (1 * food_times.length) = 2가 된다.

우리에겐 2초가 남고 위와 똑같은 방식 가장 적게 걸리는 것을 고르면 2가 된다.
우리는 이전에 1초를 사용하였기에 2 - ((2 - 1) * food_times.length) = 0이 된다.
이렇게 주어진 5초의 시간이 지났고 queue를 확인하여 남은 음식 섭취 시간을 확인한다.

첫번째 인덱스가 남았고 우리는 그것을 result list에 넣는다.
result list에 있는 값들을 index 순으로 정렬하고 남은 인덱스를 계산하여 return한다.

Food 클래스

Food 클래스를 만들어 time과 index를 저장한다.
우선순위 큐를 사용하기 위해 Comparable interface를 사용했는데, 그것에 대해서는
https://gmlwjd9405.github.io/2018/09/06/java-comparable-and-comparator.html
이 글을 읽어보면 좋을 것 같다.

Solution 클래스

우선 food_times에 합이 0인지 판단하기 위한 로직을 작성한다.
time, index 순으로 우선순위 큐에 삽입한다.
k가 되기 전까지 우선순위 큐에서 값을 poll하고 k보다 합이 커지면 인덱스 순으로 다음 섭취할 음식을 찾기 위한 로직을 구현한다.

소감

하 어렵다.
열심히 하자.