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

문제

---

* 효율성 테스트에 부분 점수가 있는 문제입니다.

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.

그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

회전판에 먹어야 할 N 개의 음식이 있다.
각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.
무지는 다음과 같은 방법으로 음식을 섭취한다.

• 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
• 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
• 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
  • 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
• 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.
무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.
각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

 

[제한사항]

• food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
• k 는 방송이 중단된 시간을 나타낸다.
• 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

[정확성 테스트 제한 사항]

• food_times 의 길이는 1 이상 2,000 이하이다.
• food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
• k는 1 이상 2,000,000 이하의 자연수이다.

[효율성 테스트 제한 사항]

• food_times 의 길이는 1 이상 200,000 이하이다.
• food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
• k는 1 이상 2 x 10^13 이하의 자연수이다.

 

 

 

풀이

---

완전탐색을 이용해서 풀 수도 있지만, 효율성에서 통과 할 수 없게 된다.

 

그림을 이용해서 설명을 하면

초기상태

1. 위와 같은 상태에서 우선 제일 적은 시간을 차지하는 것은 시간이 지나면 없어질 수 있기 때문에 시간순으로 정렬한다.

2. 시간순으로 정렬하면 위와 같이 정렬이 된다. 2번을 다 먹으려면 3번 1번도 1씩 다 없애야한다.

따라서 k >= (3 * 1) 이면, 2번 음식을 다 먹을 수 있다.

3. 2번 음식을 다 먹고나면 위와 같이 남는다. 이때의 k 는 5 - 3 = 2 가 된다.

원래의 3의 시간은 2 다 하지만 1을 먹어버렸기 때문에 1만 남아있고 1을 만큼을 더먹으면 3번 음식도 다먹을 수 있다.

k >= (2 * 1)이면, 3번 음식을 다 먹을 수 있다.

 

 

4-1. 마지막으로 위와 같이 음식이 남았고 k = 0 이 된다. 따라서 1번 음식 부터 시작을 하면 된다.

4-2. 여기서 만약 k = 0 이 아니라면, 똑같이 k >= 다먹는데 필요한 시간인지를 판단하여 시간이 부족하다면, 남은 음식을 번호순으로 정렬하여 (k %= 남은음식) 번째의 음식부터 시작하면된다.

 

 

위의 과정에서 얻을 수 있는 식을 적어보면 3개가 있다.

• k >= 다 먹는데 필요한 시간
• 다 먹는데 필요한 시간 = (남은 음식의 수) * (남은 시간)
• 남은 시간 = 총 시간 - 앞서 먹은 음식의 시간

위의 식을 이용해서 코드를 순서대로 작성하면 된다.

 

<전체코드>

import java.util.*;

class Solution {
    
    static class Food{
        
        int number;
        int amount;
        
        Food(int number, int amount){
            this.number = number;
            this.amount = amount;
        }
    }
    public int solution(int[] food_times, long k) {
        int answer = -1;
        
        int total = food_times.length;
        
        LinkedList<Food> list = new LinkedList<>();
        for(int i = 0 ; i < food_times.length ; i++){
            list.offer(new Food(i+1, food_times[i]));
        }
        
        //음식의 먹는 시간순으로 정렬
        Collections.sort(list, new Comparator<Food>(){
            @Override
            public int compare(Food f1, Food f2){
                return Integer.compare(f1.amount, f2.amount);
            }
        });
        
        //앞서 먹은 음식의 시간을 저장하기 위해 선언
        int time = 0;
        //현재의 음식부터 그 뒤의 음식을 정렬할 때 사용하기 위해 선언
        int index = 0;
        for(Food food : list){
        	//앞서 먹은 음식의 시간으 빼주어 음식을 남은 음식의 양을 저장
            long diff = food.amount - time;
            if(diff > 0){
            	//음식을 다먹으려면 걸리는 총 시간 = 남은 음식의 양 * 남은 음식의 수 
                long spend = diff * total;
                // k 가 음식을 다먹을 수 있을 때,
                if(spend <= k){
                	// 음식을 먹을 때 걸리는 시간 만큼 빼준다
                    k -= spend;
                    time = food.amount;
                }
                // k 가 음식을 다 먹을 수 없을때,
                else{
                	// 남은 음식에서 k 번째를 구하기 위해 하지만, 남은 음식보다 k 가 클경우를 대비하기위해 mod total을 해준다.
                    k %= total;
                    
                    //번호순으로 정렬하여 k 번째를 구한다.
                    list.subList(index, food_times.length).sort(new Comparator<Food>(){
                       @Override
                        public int compare(Food f1, Food f2){
                            return Integer.compare(f1.number, f2.number);
                        }
                    });
                    
                    answer = list.get(index + (int)k).number; 
                    break;
                }
            }
            
            total--;
            index++;
        }
        
        
        return answer;
    }
}

 

알고리즘의 기술보단 수학적인 이해도가 필요한 문제였다.