프로그래머스 무지의 먹방 라이브 (JAVA)

2019 KAKAO BLIND RECRUITMENT

---

무지의 먹방 라이브

---

정확성 요건을 충족시키기에 어려운 문제는 아니었지만, 효율성 요건을 충족시키는게 어려운 문제였다.

로직에 접근하는 방식은 음식을 하나 트레일러에서 내리는 데까지 필요한 음식의 양이 정해져있다는 점이었다.

테스트케이스의 경우로 설명하자면,

1번 음식 -> 3

2번 음식 -> 1

3번 음식 -> 2

 

첫 한바퀴가 도는 시점에서 2번 음식은 트레일러에서 내려가고, 소요되는 시간은 자기 자신의 남은 음식 양 * (자기보다 음식 양이 많은 음식의 개수 + 1)이 된다.

이것을 공식화하여 남은 시간이 음식 하나를 트레일러에서 내릴 시간보다 적어진다면, 반복문을 멈추고 남은 시간만큼 수동으로 세주는 것이 로직의 핵심이다.

 

1. 정렬 기준을 두개 세운다(음식의 양과 번호 순)

2. 음식의 양을 기준으로 정렬한다.

3. 위의 설명한 로직을 바탕으로 연산과정을 스킵한다.

4. 트레일러에 남아있는 음식들을 인덱스 기준으로 다시 정렬한 이후, 남은 음식의 수를 센다.

 

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    static Comparator<Food> left = new Comparator<Food>() {
		@Override
		public int compare(Food o1, Food o2) {
			return o1.quan - o2.quan;
		}
	};
	static Comparator<Food> idx = new Comparator<Food>() {
		@Override
		public int compare(Food o1, Food o2) {
			return o1.idx - o2.idx;
		}
	};
	public static int solution(int[] food_times, long k) {
		 long food_sum = 0;  // 모든 음식 먹는데 걸리는 총 시간
        for (int i = 0; i < food_times.length; i++) {
            food_sum += food_times[i];
        }

        if (food_sum <= k) return -1;
		PriorityQueue<Food> foods = new PriorityQueue<>(left);
		for (int i = 0; i < food_times.length; i++) {
			foods.add(new Food(i + 1, food_times[i]));
		}

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

		while (total + ((foods.peek().quan - previous) * length) <= k) {
			int now = foods.poll().quan;
			total += (now - previous) * length;
			length -= 1;
			previous = now;
		}

		ArrayList<Food> result = new ArrayList<>(foods);
		result.sort(idx);

		return result.get((int) ((k - total) % length)).idx;

	}

	static class Food {
		int idx;
		int quan;

		Food(int idx, int quan) {
			this.idx = idx;
			this.quan = quan;
		}
	}
}