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

문제 설명

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

문제 풀이

• 이분 탐색을 이용하여 풀이하였다.
• 풀이의 아이디어는 다음과 같다.

  • 이분 탐색의 기준은 원판의 회전 수이다.
  • 구하고자하는 값은 특정 회전일때 K시간이 나온다면 해당 회전 수 - 1을 구하는 것이다.
  • 따라서 이분 탐색의 범위는 원판의 회전수 범위(0~ 1억)이 된다.
  • 특정 회전수를 구했다면 다음 회전때 음식시간 배열을 순회하며 몇번 음식에서 K가 되는지 구해주면 된다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int solution(int[] food_times, long k) {
        //binary Search
        //회전판이 몇번 회전하는지 기준으로 구함
        //구하고자 하는 값 : 특정 회전(lo) 후 해당 회전 구간에서 k 시간이 나오는 경우
        int lo = 0;
        int hi = 0;
        for (int i = 0; i < food_times.length; i++)
            hi = Math.max(hi, food_times[i]);
        hi++;

        long sum = 0;
        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;

            sum = 0;
            for (int i = 0; i < food_times.length; i++)
                sum += food_times[i] > mid ? mid : food_times[i];

            if (sum <= k) lo = mid;
            else hi = mid;
        }

        //lo : lo번 회전 후 해당 회전 구간에서 k시간이 존재
        sum = 0;
        for (int i = 0; i < food_times.length; i++)
            sum += food_times[i] > lo ? lo : food_times[i];
        long remain = k - sum;

        for (int i = 0; i < food_times.length; i++) {
            if (food_times[i] <= lo) continue;
            if (remain-- == 0)
                return i + 1;
        }
        return -1;
    }

}