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

문제

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.
그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

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

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

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

코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(int[] food_times, long k) {
        //생존 음식 리스트를 만든다
        List<Integer> remain=IntStream.range(0, food_times.length)
            .boxed()
            .collect(Collectors.toList());
        
        //k초가 될 때까지
        while(k>0){
            //남은 음식이 없으면 -1 리턴
            if(remain.size()==0)
                return -1;
            
            //현재의 남은 모든 음식에서 reduce만큼 제거할 것이기 때문에 제거한 만큼 k를 줄인다.
            long reduce=k/remain.size();
            k%=remain.size();
            
            //남은 k초보다 음식의 수가 더 많으면 반복문 탈출
            if(reduce==0)
                break;
            
            //남은 음식들을 한 차례 돌면서
            for(int i=0; i<remain.size(); i++){
                //음식의 남은 초가 reduce보다 많으면 음식의 남은 초에서 빼준다.
                if(reduce<food_times[remain.get(i)])
                    food_times[remain.get(i)]-=reduce;
                //reduce가 더 많다면, 남은 음식 리스트에서 해당 음식을 제거하고 음식을 다 먹고 남은 초를 다시 k에 더해준다.
                else{
                    k+=reduce-food_times[remain.get(i)];
                    remain.remove(i);
                    i--;
                }
            }
        }
        
        //남은 음식의 수>k초이기 때문에 각 음식을 돌면서 초를 세준다.
        for(int i:remain){
            k--;
            //k가 0초가 된 다음 차례의 음식 리턴
            if(k==-1)
                return i+1;
        }
        
        return -1;
    }
}

해결 과정

1. 큐에 넣고 1초씩 진행했더니 예상했지만 시간초과가 떴다.

2. 음식들을 먹는 데 걸리는 시간을 y축으로 나열해서 테트리스처럼 몇 줄씩 없애고 싶었다. Boolean 타입의 시간을 열로 나열한 배열을 만들기에는 길이가 너무 길다.

3. 고민하다가 안 풀려서 다른 문제들을 풀다가 다시 왔다. 전체 남은 초/현재의 음식 수를 각각의 음식에서 빼줄 때, 음식의 남은 초가 빼야하는 초보다 작을 때 부족한 만큼을 전체 남은 초에 다시 더해주고 위의 과정을 진행해도 순서가 변하지 않는 것을 깨달았다. 현재의 남은 음식들을 첫 번째 순서부터 빼주다가 못 빼는 음식이 있으면 못뺀 초는 다시 전체 초에 더해주고 다음 번에 첫 번째 순서부터 진행하면 된다

4. 😁(카카오는 무섭다)