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

 

문제 분석

 

1. 회전테이블에   음식의 양이 다르게 담겨있는 접시들이 존재한다.

 

2. 테이블은 1초마다 회전한다.

 

3.무지는 1초마다 회전되는 접시를골라 음식을 1개 먹는다. (빈 접시가 생기면 테이블에서 없앤다.)

 

4. 이때, 네트워크가  K초의 발생했다고 쳤을때, 무지가 다시먹어야할 접시를 골라주세요.

 

4번은 말장난이다.  네트워크 K초가 발생할때 무지가 다시먹어야할 접시 라고 이해하기보단,

무지가 K+1초에 먹어야할 접시를 구한다 라고 보는것이 편하다.

 

 

문제는 아주 심플하다,  K만큼 음식을 소모하다 K+1번째를 고르면 되지만,

 

K의 데이터가 억단위를 넘는다.  즉,  1부터 K까지 일일이 음식을 소모하는 짓은 미친짓이다.

 

당연히, 이런 빅데이터를 예상하고 주어지면 효율적인 코드를 생각해야한다.

 

 

어떻게 효율적으로 짤수있을까?

 

EX)    {12, 18, 20 , 14}  의 접시가 있다고 칩시다.  K가 50이라면

 

K+1번째 접시를 어떻게 빠르게 구할까?

 

1번접시를 1빼고, 2번접시를 1빼고, 3번접시를 1빼고 ... K%4번째의 접시의 음식을빼고 

이 방식은 되지 못한다.

 

하지만 규칙은 보인다.   1 2 3 4 , 1 2 3 4 , 1 2 3 4 , ... 순대로 빼는게 보인다.

 

즉, 접시의 갯수만큼 그룹화하여 빼는것이다. 

 

그런데 그룹화하면서 빼는데 얼마만큼 그룹화 하면서 뺄까?

 

바로, 접시가 가장 작은 갯수를 기준으로 그룹화하면서뺀다.

 

예시로보자면,  12개음식이 담긴 접시를 12개를 그룹화 하면서 뺀다.

 

그렇다면 {0,6,8,2} 이다.  한번 연산으로 48초의 연산을했고,  목표 50초에 근접할수있게된다.

 

우린 이 방식을 채용할것이다.

 

 

문제 풀이

 

 

일단, 예외처리를 한번 해준다.   K+1초의 먹을 음식이없으면 -1를 반환한다.

 

 

문제분석에서 정한 로직에서  ,  음식의 양이 적은것부터 정렬해야할 필요가있다.

단, 음식의 양 대로 정렬하되,  기존에 갖던 음식의 위치 (idx)값을 저장해야만 한다.

 

이 부분은 PQ를 사용했지만,  TreeMap을 사용하셔도 되고,  List로 사용하시는 분도 있었습니다.

 

제 개인적인 생각이지만 PQ가 더 좋은 퍼포먼스를 보여주는것같습니다. PQ의 값이 들어올때마다 정렬해주는 

로직은 다른 자료구조보다 효율적이기 때문입니다.

 

 

int  cycle :  진행한 회전수 

long  time :  진행한 경과 시간

 

진행조건은    남은시간 (k-time)이   음식량- 회전수* 전체 음식만큼 크거나 같은지이다.

 

True라면,  cycle과 time을 갱신하고 빈접시는 빼준다.

 

 

모든 반복을 완료햇다면  PQ를  다시 Array로 만든뒤에,  다시한번 정렬한다.

 

정렬기준은 원래있었던 음식의 위치순대로다.

 

음식의 위치순대로 정렬한뒤,  K-time 번째를 탐색한다. 

 

빈접시를 뺀  ArrayList의 사이즈가  remain과  맞지않을수가 있다.  %연산을해줘야한다.

 

import java.util.ArrayList;
import java.util.PriorityQueue;
 
class Solution {
 
    public int solution(int[] food_times, long k) {
 
 
        long sum = 0;
        for (int foodTime : food_times)
            sum += foodTime;
        if (sum <= k)
            return -1;
        
 
        PriorityQueue<Food> queue = new PriorityQueue<>((a, b) -> a.fTimes - b.fTimes);
        for (int i = 0; i < food_times.length; i++) {
            queue.add(new Food(i, food_times[i]));
        }
 
        int cycle = 0;
        long time = 0;
 
        while ((queue.peek().fTimes - cycle) * (long) queue.size() <= (k - time)) {
            int foodsCnt = queue.size();
            Food food = queue.poll();
            time += (food.fTimes - cycle) * (long) foodsCnt;
            cycle = food.fTimes;
        }
 
        ArrayList<Food> list = new ArrayList<>(queue);
        list.sort((a, b) -> a.index - b.index);
 
        long remain = k - time;
        int index = (int) (remain % list.size());
 
        return list.get(index).index + 1;
    }
 
    class Food {
        int index;
        int fTimes;
 
        public Food(int index, int fTimes) {
            this.index = index;
            this.fTimes = fTimes;
        }
    }
}