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

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

먹을 음식이 food_times 배열로 들어오고, 매 초마다 food_times의 각 음식을 1초동안 먹는다.

i번째 음식을 먹으면 food_times[i]는 1 감소하고, 0이 되면 다음 반복에서 i번째는 건너뛴다.

k초동안 음식을 먹은 후 다음 먹을 음식의 번호를 반환하는 문제이다.

위의 효율성 테스트 제한 사항을 보면 당연히 시뮬레이션 형식은 무리임을 파악할 수 있다.

그래서 생각한 방법이 food_times를 정렬한 후, 음식을 하나씩 통째로 먹는 방법이었다.

{3, 1, 2}를 정렬하면 {1, 2, 3}이 되고, 가장 금방 사라져버리는 1부터 통째로 먹는 것이다.

1을 통째로 먹어버리면 배열에 남은 음식 개수는 배열 크기 - 1 (2개)가 되고, 시간은 배열 크기 * 1 (3초) 만큼 증가한다.

그 다음으로 2를 통째로 먹어버리면 남은 음식 개수는 배열 크기 - 2 (1개)가 되고, 시간은 (배열 크기 - 1) * (2 - 1) (2초)가 증가한다.

이 방법을 일반화해보자.

음식 배열의 크기가 n이라 하면

하나를 통째로 먹을 경우 시간은
(n - 먹은 음식 수) * (현재 음식의 시간 - 현재까지 먹은 양) 만큼 증가한다.

{15, 10, 5, 50, 40, 80}을 예로 들어보면
정렬 - {5, 10, 15, 40, 50, 80}

가장 금방 먹는 5를 통째로 먹는다면 시간은
(6 - 0) * (5 - 0) = 30초만큼 증가한다. (먹은 양 5)

다음으로 10을 통째로 먹는다면 시간은
(6 - 1) * (10 - 5) = 25초만큼 증가한다. (먹은 양 10)

다음으로 15를 통째로 먹는다면 시간은
(6 - 2) * (15 - 10) = 20초 만큼 증가한다. (먹은 양 15)

다음으로 40을 통째로 먹는다면 시간은
(6 - 3) * (40 - 15) = 75초 만큼 증가한다. (먹은 양 40)

이런 느낌이다.

그럼 이제 중요한 것은 다음 음식을 먹었을 때 시간이 k초를 넘어가는 경우이다.

위의 예시에서, 15까지 통째로 먹으면 시간은 75초가 되고 배열상태는 아래와 같다

{0, 0, 0, 35, 25, 65}

(참고로 실제로 배열의 값을 수정하지는 않고, 현재 값 - 먹은 양으로 판단한다.)

위 예시에서 k=100으로 주어졌다면 어떻게 해야하나

다음으로 가장 적은 25를 통째로 먹어버리면 시간은 150초가 되어 k를 넘어간다.

따라서 다음 먹은 시간이 k를 넘어가는 경우, 먹어버리지 않고 현재 상태에서 답을 반환해야 한다.

다음 먹을 음식을 걸러내는 방법은 간단하다.

현재 먹을 수 있는 음식은 (n - 먹은 음식 수), 위의 예시에선 3개이다.

그럼 간단하게 (k - 현재까지 시간) % 남은 음식 수 만큼 남아있는 음식들의 번호를 세면 된다

현재 배열이 {0, 0, 0, 35, 25, 65}이고 현재 시간은 75초, k=100이다.

그럼 (100 - 75) % 3 = 25 % 3 = 1이므로 다 먹어 버린 음식을 제외하고 35, 25, 65인 것들 중 1번째에 해당하는 35에서 방송이 중단되고, 25가 다음 먹을 음식이 된다.

과정을 그림으로 보면 아래와 같다.

class Solution {
    fun solution(food_times: IntArray, k: Long): Int {
        val size = food_times.size
        val sorted = food_times.sortedArray()
        var eaten = 0L
        var time = 0L

        for(i in sorted.indices){
            if(time + (size - i) * (sorted[i] - eaten) > k){
                val moves = (k - time) % (size - i)
                var tmp = 0L
                for(j in food_times.indices){
                    if(food_times[j] - eaten <= 0) continue
                    if(tmp++ >= moves){
                        return j + 1
                    }
                }
            }
            time += (size - i) * (sorted[i] - eaten)
            eaten = sorted[i].toLong()
        }

        return -1
    }
}