Programmers 42891: 무지의 먹방 라이브

문제 조건

회전판에 먹어야 할 1~N의 음식이 있다. 각 음식을 섭취하는데 일정 시간이 소요된다.

• 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
• 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. => 원형 큐
• 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.

무지가 먹방을 시작한 지 K 초 후에 방송이 잠시 중단되었는데, 다시 방송을 이어갈 때 섭취할 음식의 번호를 구하는 문제이다.

 

먼저 k가 음식의 갯수보다 큰지 작은지 생각해 보아야 한다.

• k < food_times.length: (k+1) 번째 음식을 무조건 리턴
• k > food_times.length: 맨 처음 들어있는 음식의 시간만큼 사이클을 돌 수 있는 경우
  • 한 cycle을 돌 수 있는 경우: k 시간에서 사이클을 도는 시간만큼 바로 빼준다
  • 한 cycle 전에 끝나는 경우: 큐에 있는 index를 크기순으로 정렬했을 때 몇번째 위치를 리턴해야 하는지 생각해본다

 

음.. 글로 설명하니까 좀 어려워 보이는데,,,,

프로그래머스 질문하기에 나와있는 예시를 한 번 시뮬레이션 해 보면

food_times=[4,2,3,6,7,1,5,8] k=27 => answer = 5

 

food = [(0, 4), (1, 2), (2, 3), (3, 6), (4, 7), (5, 1), (6, 5), (7, 8)] 이고 가장 작은 값을 가진 1만큼의 사이클을 돈다고 하면 1*8=8 => k-8=19

food = [(0, 4), (1, 2), (2, 3), (3, 6), (4, 7), (6, 5), (7, 8)] 그 다음 가장 작은 2-1 = 1만큼의 사이클을 돌면 1*7=7 => 19-7=12

food = [(0, 4), (2, 3), (3, 6), (4, 7), (6, 5), (7, 8)] 그 다음 가장 작은 3-2 = 1만큼의 사이클을 돌면 1*6=6 => 12-6=6

food = [(0, 4), (3, 6), (4, 7), (6, 5), (7, 8)] 그 다음 가장 작은 4-3 = 1만큼의 사이클을 돌면 1*5=5 => 6-5=1

food = [(3, 6), (4, 7), (6, 5), (7, 8)] 마지막으로 사이클을 온전히 다 돌지 못하기 때문에 1+1번째 요소를 찾으면 (4,7)이고 해당 answer=5이다.

 

즉, 한 개의 사이클을 온전히 돌 수 있다면 그 요소는 결국 리스트에서 사라지기 때문에 위치가 영향을 주지 않고,

food_times가 가장 작은 순으로 사이클을 돌아야 하기 때문에 자료구조는 priority queue가 적합하다.

 

한 개의 사이클을 온전히 돌 수 없다면 맨 처음 들어왔던 food_times의 인덱스 순으로 순회한다.

 

아래는 그 풀이이다.

import java.util.*;
import java.util.stream.Collectors;
class Solution {
	public int solution(int[] food_times, long k) {
		int length = food_times.length;

		if (k < length) {
			return (int) (k % length) + 1;
		}

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

		long minus = 0;
		while (!queue.isEmpty()) {
			Food now = queue.peek();
			long cycle = (long) (now.left - minus) * queue.size();
			if (k - cycle >= 0) { // 한바퀴
				k -= cycle;
				minus = now.left;
				queue.poll();

			} else { // 중간에 멈춤
				k %= queue.size();
				return queue.stream().mapToInt(food -> food.index).sorted().skip(k).findFirst().getAsInt() + 1;
			}
		}

		return -1;
	}
}

class Food implements Comparable<Food> {
	int index;
	int left;

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

	@Override
	public int compareTo(Food o) {
		return Integer.compare(left, o.left);
	}

	@Override
	public String toString() {
		return "(" + index + ", " + left + ")";
	}
}