[프로그래머스] 무지의 먹방 라이브 (자바)

 

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

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

정확성 약 42%, 효율성 약 5.5%의 정답률인 문제입니다.

이 문제는 접근 방법이 어렵지 않아서 효율성까지 노리고 풀었습니다.

PriorityQueue + List로 했는데 복잡도가 너무 높아서 효율성은 통과되지 못했고,

다른 코드를 보고 공부해서 다시 작성해봤습니다.

 

Food형 리스트에 모든 음식을 넣고, 음식의 양으로 정렬합니다.

 

이렇게 정렬 후 색칠된 칸을 줄 단위로 세서 k에서 점점 빼는 방식입니다.

[3,3,3,5], k = 13의 경우 3*4 = 12가 나오고 13 - 12 = 1, 따라서 4가 정답입니다.

[2,3,3,5], k = 13의 경우 2*4 = 8이 나오고 13 - 8 = 5

(3-2) * 3 = 3, 5 - 3 = 2가 나오고 따라서 4가 정답입니다. 

 

코드를 통해 이해해 봅시다.

---

메소드

int solution

k초에 음식을 먹고 다음에 먹어야 할 음식을 반환해야 하므로 k++를 해줍니다.

list에 Food를 채워주고 음식의 양으로 오름차순 정렬해줍니다.

 

time은 이전 음식이 가진 양입니다. 

위 그림을 봤을 때 1칸씩 차이가 나지만 만약 2칸씩 차이가 난다면

2(현재 음식의 양 - 이전 음식의 양) * (남아있는 음식의 수)를 해줘야 합니다.

 

index는 위 그림에서 세로줄로 이해하면 됩니다. 

음식을 처리할 때마다 한 줄씩 밀어줍니다.

 

리스트에서 처리가 끝난(음식을 모두 먹은) 부분을 제외하고 음식의 숫자 순으로 정렬해줍니다.

subList와 index를 활용했습니다.

[2,2,4,5,8,8,8,9]에서 5까지 처리가 됐다면 녹색 부분만 정렬하는 것입니다.

그 후 k를 나머지 연산하여 반환해줍니다.

만약 음식을 다 먹었는데 시간이 남았다면 -1을 반환합니다.

 

Food

음식의 번호인 number와 양인 amount를 가집니다.

 

import java.util.*;

public class Solution {

	public int solution(int[] food_times, long k) {
		LinkedList<Food> list = new LinkedList<Food>();
		int n = food_times.length;

		for(int i = 0; i < n; i++) 
			list.add(new Food(i+1, food_times[i]));

		Collections.sort(list, new Comparator<Food>() {
			public int compare(Food f0, Food f1) {
				return Integer.compare(f0.amount, f1.amount);
			}
		});
		
		
		int time = 0;
		int index = 0;
		
		for(Food f : list) {
			long diff = f.amount - time;
			if(diff != 0) {
				long spend = diff * n;
				if(spend <= k) {
					k -= spend;
					time = f.amount;
				}
				else {
					k %= n;
					list.subList(index, food_times.length).sort(new Comparator<Food>() {
						public int compare(Food o1, Food o2) {
							return o1.number-o2.number;
						}
					});
					
					return list.get(index+(int) k).number;
				}
			}
			index++;
			n--;
		}

		return -1;
	}

	class Food{
		int number, amount;

		Food(int number, int amount) {
			this.number = number;
			this.amount = amount;
		}
	}

}