p.퍼즐게임챌린지

 

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

프로그래머스

 

 

 

이 문제는 이분 탐색을 활용해 난이도 조정을 통해
주어진 시간 제한 안에서 플레이 가능한 최소 레벨을 구하는 문제를 해결한다.
solution 메서드는 난이도의 범위를 설정하고,
이분 탐색을 통해 해당 레벨에서 플레이 시간이 조건을 만족하는지를 검사하며
최적의 레벨을 찾는다.

calculate 메서드는 특정 레벨에서 플레이 시간을 계산하는 함수다.
난이도가 레벨보다 높은 경우,
난이도 차이만큼 추가 플레이 시간이 발생하며,
이 시간은 현재 및 이전 구간의 시간을 기반으로 계산된다.
전체 플레이 시간이 제한 시간을 초과하면 즉시 false를 반환하고,
끝까지 초과하지 않으면 true를 반환한다.

solution 메서드는 난이도의 최댓값과 최솟값을 기반으로 이분 탐색 범위를 초기화하며,
mid 값을 기준으로 calculate 메서드를 호출해 플레이 시간이 조건을 만족하는지를 판단한다.
조건이 만족되면 난이도를 낮추어 탐색 범위를 줄이고,
조건이 만족되지 않으면 난이도를 높여 탐색 범위를 조정한다.
탐색이 끝나면 최소 난이도를 반환한다.

 

 

class Solution {
    boolean calculate(int level,int[] diffs, int[] times, long limit){
        long playTime = 0;
        for(int i = 0 ; i < diffs.length ; i++){
            if(limit < playTime) return false;
            if(level < diffs[i]) 
                playTime += (long)(diffs[i]-level)*(long)(times[i-1]+times[i]); 
            playTime += times[i];
            
        }
        if(limit < playTime) return false;
        return true; 
    }
    public int solution(int[] diffs, int[] times, long limit) {
        int left = 1000000;
        int right = -1;
        for(int i = 0 ; i < diffs.length ; i++){
            right = Math.max(right,diffs[i]);
            left = Math.min(left,diffs[i]);
        }
        while(left<right){
            int mid = (left + right) / 2;
            if(calculate(mid,diffs,times,limit)){ 
                right = mid;
            }
            else left = mid + 1;
        }
        return right;
    }
}