[프로그래머스] 무지의 먹방 라이브 / 2019 KAKAO BLIND RECRUITMENT - JAVA

🖇️ 문제 링크

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

효율성 테스트에 부분 점수가 있는 문제입니다. 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다.

https://programmers.co.kr/learn/courses/30/lessons/42891

 

---

📝 문제 분석

하나씩 음식 먹는 것을 계산하다보면 효율성 테스트는 통과할 수 없습니다.

먹는데 걸리는 시간을 기준으로 오름차순 정렬을 한 뒤, 음식 하나씩 없애버리는 방법으로 진행합니다.

for(; i < n; i++) {
    int d = (i == 0) ? foods.get(i)[0] : foods.get(i)[0] - foods.get(i - 1)[0];
    // d * (n - i) -> 먹는데 걸리는 시간 작은 거부터 하나씩 지움, 제일 작은거 만큼 전체에서 뺀다
    if(k < (long) d * (n - i)) break;
    k -= (long) d * (n - i);
}

가장 빨리 먹을 수 있는 음식이 3의 시간이 걸린다면, 총 세 바퀴를 먹어야 없앨 수 있습니다.

3 * (남아 있는 음식의 수)를 k에서 빼줍니다.

그리고 다음 없앨 음식은 똑같이 세 바퀴를 돌았기 때문에 3이 줄어있을 것입니다.

더 이상 없앨 수 없을 때 까지 진행합니다.

 

---

⌨️ 코드

import java.util.*;

class Solution {
    public int solution(int[] food_times, long k) {
        // foods -> 먹는데 걸리는 시간, 인덱스
        ArrayList<int[]> foods = new ArrayList<>();
        int n = food_times.length;
        for(int i = 0; i < n; i++)
            foods.add(new int[]{food_times[i], i + 1});
        // 먹는데 걸리는 시간 오름차순으로 정렬
        foods.sort(Comparator.comparingInt(f -> f[0]));
        int i = 0;
        for(; i < n; i++) {
            int d = (i == 0) ? foods.get(i)[0] : foods.get(i)[0] - foods.get(i - 1)[0];
            // d * (n - i) -> 먹는데 걸리는 시간 작은 거부터 하나씩 지움, 제일 작은거 만큼 전체에서 뺀다
            if(k < (long) d * (n - i)) break;
            k -= (long) d * (n - i);
        }
        // 전부 다먹었으면 -1
        if(i == n) return -1;
        // i - 1위치까지만 다 먹었으니까, 다음 꺼부터는 인덱스로 정렬 시킴
        foods.subList(i, n).sort(Comparator.comparingInt(f -> f[1]));
        // 남은 k초만큼 1초씩 돌아가면서 확인
        return foods.get((int) (i + k % (n - i)))[1];
    }
}

 

 

Uploaded by Notion2Tistory v1.1.0