[java] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

풀이

1. level의 최댓값과 최솟값을 설정한다 - max_level = Array.stream(diffs).max().getAsInt(); - min_level = 1;    2. 퍼즐을 풀이하며 누적된 시간을 cum_time에 저장한다. 초기값은 0  3.이진탐색을 사용해 범위를 반씩 좁혀가며 해결한다 - binarySearch(난이도, 소요시간, 레벨) - cum_time > limit 이면 min_level을 중위값으로 높인다 - cum_time < limit 이면 max_level을 중위값으로 내린다

회고

result의 범위가 너무 넓은 경우에는 이진탐색을 해야 엄청난 양의 계산을 피할 수 있다

코드 (접은 글)

import java.util.*;


class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int max_level = Arrays.stream(diffs).max().getAsInt();
        int min_level = 1;
        long cum_time = 0;
        
        while(min_level < max_level) {
            int level = (min_level + max_level) / 2;
            cum_time = calc_time(diffs, times, level);
            
            if (cum_time <= limit) max_level = level;
            else min_level = level + 1;
        }
        
        return max_level;
    }
    
    private long calc_time(int[] diffs, int[] times, int level) {
        long time = 0;
        for(int i=0; i<diffs.length; i++) {
            if(diffs[i] <= level) {
                time += times[i];
            } else {
                int time_prev = i == 0 ? 0 : times[i-1]; 
                int time_cur = times[i];
                time += (time_prev + time_cur) * (diffs[i] - level) + time_cur;
            } 
        }
        return time;
    }
}