[이코테][Java] 무지의 먹방 라이브

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42891

프로그래머스

 

문제 설명

무지가 1부터 N번까지의 음식을 음식번호가 증가하는 순서대로 먹기 시작한다.

먹방을 시작한 지 K초 후에 네트워크 장애로 인해 방송이 잠시 중단된 후, 다시 먹기 시작할 때 몇 번 음식부터 먹어야 하는지 구한다.

만약 더 섭취해야 할 음식이 없다면 -1을 반환한다.

 

입력조건

• 각 음식을 모두 먹는데 필요한 시간이 들어있는 배열 food_times
• 방송이 중단되 시간 k

출력조건

• k

입출력 예시

입력예시	출력예시
[3, 1, 2] 5	1

 

 

 

 

문제 풀이

 

실패한 풀이

순차적으로 완전 탐색으로 음식을 섭취하면서  (k+1)초일 때 먹어야 하는 음식의 번호를 찾아 반환한다.

하지만 이 풀이는 효율성 테스트에서 모두 실패(시간초과)를 받았다.

또한 k초가 지난 후 idx에 1을 더한 값을 반환한다. 그런데 여기서 food_times[idx+1] = 0 일 경우에는 해당 번호의 음식을 먹을 수 없는데 이 경우를 생각하지 못했다.

class Solution {
    public int solution(int[] food_times, long k) {
        int idx = 0;
        int sum = 0;

        //음식의 총 섭취량
        for (int foodTime : food_times) {
            sum += foodTime;
        }

        //총 섭취량이 k보다 작거나 같으면 -1 반환
        if (sum <= k) {
            return -1;
        }

        while(k > 0) {
            if(food_times[idx] != 0) {  //해당 음식이 아직 남아있다면, 그 음식을 섭취한다.
                food_times[idx]--;
                k--;
            }

            //음식번호 변경
            if(idx == food_times.length - 1) {  //현재 위치가 n번 음식이라면 처음으로 다시 돌아간다.
                idx = 0;
            } else {    //그렇지 않으면 음식 번호 증가
                idx++;
            }
        }
        return idx + 1;
    }
}

 

 

 

 

성공한 풀이

다른 분의 풀이를 참고해서 문제를 풀었다. 코드를 구현하기 전에 풀이 방법을 설명하면 다음과 같다.

1. 음식을 먹는데 필요한 시간 순서대로 오름차순 정렬한다.
2. diff = (현재 음식을 먹는데 걸리는 시간) - (현재 시간)를 구한다.
   
   • diff : 이전 음식과 현재음식을 먹는데 필요한 시간의 높이 차. 즉, 아래 그림에서 세로 부분을 의미
3. spend = diff × (남아있는 음식 종류의 개수) 를 구한다.
   • 남아있는 음식 종류의 개수 : 아래 그림에서 가로 부분을 의미
   • spend <= k 일 경우, k 에서 spend를 빼주고 남아있는 음식 종류의 개수(n)와 현재시간을 변경한다.
   • spend > k 일 경우, 순회를 중단하고 남은 음식들을 원래 순서대로 다시 정렬해서 k초 후에 먹게될 음식을 구한다.

 

예시1) food_times = {3, 1, 2}, k=5

그림으로 그려보면 왼쪽 그림과 같아서 k초가 지난 후 먹게 될 음식은 1번이다.

이를 음식을 먹는데 걸리는 시간 순으로 오름차순 정렬하면 오른쪽 그림과 같다.

1) 현재 음식번호 = 2 / 현재 음식을 먹는데 걸리는 시간 = 1 / 현재시간 = 0 / k = 5 / n = 3

• diff = 1 - 0 = 1
• spend = 1 * 3(n) = 3
• 3(spend) <= 5(k) 이므로 k = 5 - 3 = 2, n = 2 가 된다.

2) 현재 음식번호 = 3 / 현재 음식을 먹는데 걸리는 시간 = 2 / 현재시간 = 1 / k = 2 / n = 2

• diff = 2 - 1 = 1
• spend = 1 * 2(n) = 2
• 2(spend) <= 2(k) 이므로 k = 2 - 2 = 0, n = 1 가 된다. 

3) 현재 음식번호 = 1 / 현재 음식을 먹는데 걸리는 시간 = 3 / 현재시간 = 2 / k = 0 / n = 1

• diff = 3 - 2 = 1
• spend = 1 * 1 = 1
• 1(spend > 0(k) 이므로 남아있는 음식을 원래 순서대로 정렬해서 k초가 지난 후 먹게 될 음식을 구한다.
• 여기서는 k = 0 , 남아있는 음식은 1번밖에 없기 때문에 k초가 지난 후 먹게 될 음식은 1번이 된다.

 

 

예시 2) food_times = {3, 5, 1, 6, 5, 3}, k=20

1) 현재 음식번호 = 3 / 현재 음식을 먹는데 걸리는 시간 = 1 / 현재시간 = 0 / k = 20 / n = 6

• diff = 1 - 0 = 1
• spend = 1 * 6(n) = 6
• 6(spend) <= 20(k) 이므로 k = 20 - 6 = 14, n = 5 가 된다.

2) 현재 음식번호 = 1 / 현재 음식을 먹는데 걸리는 시간 = 3 / 현재시간 = 1 / k = 14 / n = 5

• diff = 3 - 1 = 2
• spend = 2 * 5(n) = 10
• 10(spend) <= 14(k) 이므로 k = 14 - 10 = 4, n = 4 가 된다.

3) 현재 음식번호 = 6 / 현재 음식을 먹는데 걸리는 시간 = 3/ 현재시간 = 3 / k = 4 / n = 4

• diff = 3 - 3 = 0
• spend = 0 * 4 = 0 이므로 skip

4) 현재 음식번호 = 2 / 현재 음식을 먹는데 걸리는 시간 = 5 / 현재시간 = 3 / k = 4 / n = 3

• diff = 5 - 3 = 2
• spend = 2 * 3(n) = 6
• 6(spend) <= 4(k) 이므로 남아있는 음식들을 원래 순서대로 정렬한 후 k초가 지난 후 먹게 될 음식을 구한다.
  
  • 남아있는 음식들2, 5, 4를 원래 순서대로 다시 정렬하면 2, 4, 5이다.
  • k % n = 4 % 3 = 1이 된다.
  • 따라서 k초에 먹게 될 음식은 1번 음식이고, k+1초에 먹게 될 음식은 4번이다.

 

 

위 풀이 방법을 코드로 작성하면 아래와 같다.

import java.util.*;

class Solution {
    //음식을 (음식을 먹는데 걸리는 시간, 음식 순서) 순으로 묶어서 저장
    class Food {
        int time;
        int idx;

        Food(int time, int idx) {
            this.time = time;
            this.idx = idx;
        }
    }


    public int solution(int[] food_times, long k) {

        LinkedList<Food> foods = new LinkedList<>();
        int n = food_times.length;  //음식의 총 개수
        for (int i = 0; i < n; i++) {   //(음식을 먹는데 걸리는 시간, 음식 순서) 순으로 리스트에 저장
            foods.add(new Food(food_times[i], i + 1));
        }

        Collections.sort(foods, ((o1, o2) -> o1.time - o2.time));   //음식을 먹는데 걸리는 시간 순으로 오름차순 정렬

        int pretime = 0;    //현재 음식을 먹는데 걸리는 시간
        int idx = 0;    //현재 음식 순서
        for (Food f : foods) {
            long diff = f.time - pretime;   //(현재 음식을 먹는데 걸리는 시간) - (현재 시간)

            if (diff != 0) {
                long spend = diff * n;
                if (spend <= k) {
                    k -= spend;
                    pretime = f.time;
                } else {
                    k %= n;
                    foods.subList(idx, food_times.length).sort((o1, o2) -> o1.idx - o2.idx);    //남은 음식들을 원래 순서대로 다시 정렬
                    return foods.get(idx + (int) k).idx;
                }

            }
            idx++;
            n--;
        }

        return -1;
    }
}

---

 

[참고]

- 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈

- https://www.youtube.com/watch?v=4MWxAt4fx5I