[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 무지의 먹방 라이브 (Java)

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 무지의 먹방 라이브 : https://programmers.co.kr/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브 | 프로그래머스

 

 

이번 문제는 효율성 테스트가 있는 문제였다.

회전판(배열)에는 N개의 음식이 있고, 각 음식에는 1부터 N까지 번호가 붙어있다.

무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.

K초 후에 무지가 몇 번 음식을 먹을 차례인지 구하는 문제다.

 

단순하게 생각하면 while문으로 시간을 흐르게 하면서 각 음식의 값을 1씩 낮추면서 반복하면 된다.

하지만 음식의 개수가 최대 200,000이며, k는 최대 2 × 10^13이다.

따라서 순차 탐색으로는 무조건 시간 초과가 날 것이다.

 

우리가 알고 싶은 것은 K초 후에 무지가 어떤 음식을 먹느냐이다.

K초 근처에서의 값이 중요하지, K초까지 가는 모든 값이 중요한 것은 아니다.

따라서 시간을 증가할 때 음식의 남은 개수만큼 더해주며 증가시킨다.

 

우선 food_times를 오름차순으로 정렬시킨 뒤, 배열을 따로 저장해준다.

현재 시간(time)에 남은 음식의 수를 더한 값이 K보다 작다면 (while문 조건), 현재 시간에 남은 음식의 수를 더해준다.

이 뜻은 무지가 모든 음식을 먹으면서 한 바퀴를 돌았다는 뜻이 된다.

무지가 몇 바퀴를 돌았는지는 num 변수로 관리한다.

정렬된 배열의 각각의 값에서 num 변수를 뺀 값이 0보다 작다면 음식을 다 먹은 것으로 생각한다.

 

while문이 끝난다면 이제 K초 근처에 다가왔다는 뜻이다.

이제 남은 음식 중에 K초 후에 몇 번 음식을 먹게 되는지 순차 검색으로 탐색한다.

 

관리해줘야 할 변수가 많아서 꽤나 헷갈렸지만, 아이디어 자체는 그리 어려운 편이 아니었다.

코드로 보면 좀 더 이해하기 편할 것이다.

 

 

총 걸린 시간 : 50분

난이도 : ★★★☆☆

 

코드

import java.util.Arrays;

class Solution {
    public int solution(int[] food_times, long k) {
        int n = food_times.length;
        int[] sortFood = sort(n, food_times);

        int food = n; // 섭취할 수 있는 음식의 수
        int idx = 0, num = 0;
        long time = 0; // 총 걸린 시간
        while (time + food <= k) {
            time += food;
            num++;
            for (int i = idx; i < n; i++) {
                if (sortFood[i] == num) {
                    idx++;
                    food--;
                } else break;
            }
            if (food == 0) return -1; // 섭취할 수 있는 음식이 없다면
        }

        long count = k - time + 1;
        for (int i = 0; i < n; i++) {
            if (food_times[i] - num > 0) {
                if (--count == 0) {
                    return i + 1;
                }
            }
        }
        return -1;
    }

    private int[] sort(int n, int[] food_times) {
        int[] result = new int[n];
        System.arraycopy(food_times, 0, result, 0, n);
        Arrays.sort(result);
        return result;
    }
}