[프로그래머스]무지의 먹방 라이브 - JAVA

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

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

풀이

🪑 다른 분의 풀이를 참고하여 풀었던 문제였다. 처음에는 K를 기준으로 순회를 하며 풀었는데 정확성 부분에서는 통과를 했지만, 효율성 부분에서 통과하지 못했다.

풀이를 참고하고 보니, 절대 생각치 못했던 방법이었다. 아예 기준을 바꾸어서 생각해 주어야 하는 문제였다.

 

📝 문제를 정리해 보자!

• 무지가 1번부터 N번까지의 음식을 한 음식당 1초의 시간을 사용하여 먹기 시작한다.
• 번호가 증가하는 순서대로 먹기 시작하며 마지막 번호까지 먹고 난 후에는 다시 1번 음식으로 돌아온다.
• K초 후에 네트워크 장애로 인해 음식 먹방은 중단한 다음 다시 먹방을 시작할 때 몇 번 음식부터 시작해야 하는지 구한다.

 

 

🔧 문제를 풀어 보자!

1. 음식을 시간 순서대로 정렬한다.
2. 현재 음식을 먹는데 필요한 시간에서 현재 시간을 뺀 값에 남아있는 음식의 종류를 곱하여 현재 시간을 재 설정해 준다.
3. 만약 현재 음식을 먹는데 요구되는 구한 값이 K보다 크다면 해당 음식을 먹는데 네트워크 장애가 발생한다는 의미이므로 남아있는 음식의 종류 중에서 다시 먹어야 하는 음식의 인덱스를 찾아준다.

 

 

🔹 음식을 시간 순서대로 정렬한다.

• 예제 입력을 정렬하면 위와 같아 진다.

 

 

🔹 현재 음식을 먹는데 필요한 시간에서 현재 시간을 뺀 값에 남아있는 음식의 종류를 곱하여 현재 시간을 재 설정해 준다.

• 음식을 먹는데 필요한 시간이 제일 작은 음식부터 연산을 시작하게 된다.
• 현재 음식을 먹는데 필요한 시간에서 현재 시간을 뺀 값은 위의 표를 참고하면, 이전 음식을 먹는데 필요한 시간과의 높이 차가 된다.
• 앞서 구한 높이 차에 남아있는 음식의 종류를 곱하여 해당 시간 만큼 모든 음식을 먹어준다는 의미이다.

 

 

🔹 만약 현재 음식을 먹는데 요구되는 구한 값이 K보다 크다면 해당 음식을 먹는데 네트워크 장애가 발생한다는 의미이므로 남아있는 음식의 종류 중에서 다시 먹어야 하는 음식의 인덱스를 찾아준다.

• 현재 음식을 먹는데 요구되는 구한 값이 K보다 크다면 K시간 내에 해당 음식을 먹을 수 없다. 즉, 네트워크 장애가 발생하는 시간대가 포함된다는 의미이다.
• 그러므로 남아있는 음식의 종류중에서 K번째에 먹어야 하는 음식을 찾아주면 된다.
• K를 남아있는 음식의 종류로 나눈 나머지 값을 사용하여 몇 번째 인덱스 인지 찾아줄 수 있다.
• 이때 남아있는 음식은 현재 시간 순서대로 정렬된 상태이다. 다시 원래 상태로 되돌려 주어야 하기 때문에 음식의 번호로 재 정렬해 준 다음 인덱스를 찾아 반환해 주면 된다.
• 탐색 동안 인덱스를 찾지 못하였다면 -1을 출력한다.

 

코드

import java.util.*;
 
class Solution {
    public int solution(int[] food_times, long k) {
        LinkedList<Food> list = new LinkedList<>();
        int len = food_times.length;
        for(int i = 0; i < len; i++) {
            list.add(new Food(i + 1, food_times[i]));
        }
        Collections.sort(list, (o1, o2) -> o1.time - o2.time);
        
        int current_time = 0;
        int idx = 0;
        for(Food f : list) {
            long diff = f.time - current_time;
            if(diff != 0) {
                long spend = diff * len;
                if(spend <= k) {
                    k -= spend;
                    current_time = f.time;
                } else {
                    k %= len;
                    list.subList(idx, food_times.length).sort((o1, o2) -> o1.num - o2.num);
                    return list.get(idx + (int)k).num;
                }
            }
            idx++;
            len--;
        }
        return -1;
    }
    
    public class Food {
        int num, time;
        
        public Food(int num, int time) {
            this.num = num;
            this.time = time;
        }
    }
}

 

 

reference