[프로그래머스] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

코드 힌트

1. 이진 탐색을 통한 레벨 탐색
   • 목표는 작업을 완료하는 데 필요한 시간(curTime)이 제한 시간(limit)을 넘지 않도록 레벨을 찾아내는 것입니다.
   • 이진 탐색은 레벨(level)을 조정해가며 가장 낮은 가능한 레벨을 찾습니다.
   • left는 1에서 시작하고, right는 주어진 작업의 최대 난이도로 설정됩니다. mid는 left와 right의 중간값으로, 작업을 완료할 수 있는지 여부를 확인하기 위한 임시 레벨로 사용됩니다.
2. 계산 로직
   • 주어진 레벨 mid보다 난이도가 높은 작업들은 해당 레벨로 난이도를 줄여야 하므로 추가적인 시간을 소모하게 됩니다.
   • 이때, 이전 작업(times[i-1])과 현재 작업(times[i])의 소요 시간이 더해져야 합니다.
   • 모든 작업을 완료한 시간이 제한 시간을 초과하면, 현재 레벨에서는 작업을 완료할 수 없다는 뜻입니다. 따라서 left 값을 올려 더 높은 레벨을 시도합니다.
3. 최종 반환 값
   • 이진 탐색이 끝나면 left 값이 가장 낮은 가능한 레벨을 가리키며, 이 값이 최적의 레벨로 반환됩니다.

---

정답은 더보기 클릭

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        // 이진 탐색을 위한 초기 범위를 설정합니다.
        long left = 1;
        long right = getMaxLevel(diffs); // 문제에서 가능한 최대 난이도
        
        // 이진 탐색을 통해 가능한 최소의 레벨을 찾습니다.
        while(left < right){
            long mid = (left + right) >> 1; // 중간 레벨을 계산합니다.
            
            // 해당 중간 레벨에서 주어진 시간 제한 내에 클리어가 가능한지 확인합니다.
            if(isImPossible(diffs, times, mid, limit)){
                left = mid + 1; // 불가능하다면 더 높은 레벨을 탐색합니다.
            }else{
                right = mid; // 가능하다면 더 낮은 레벨을 탐색합니다.
            }
        }
        
        // 최종적으로 찾은 가능한 최소 레벨을 반환합니다.
        return (int) left;
    }
    
    // 주어진 레벨에서 주어진 시간 제한을 초과하는지 여부를 확인하는 메서드입니다.
    public boolean isImPossible(int[] diffs, int[] times, long level, long limit) {
        long curTime = 0;
        
        // 각 구간의 난이도와 시간을 비교하여, 주어진 레벨에서 클리어 가능한지 확인합니다.
        for (int i = 0; i < diffs.length; i++) {
            // 현재 난이도가 주어진 레벨보다 높으면 그 차이만큼 추가 시간을 소모합니다.
            if (diffs[i] > level) {
                curTime += (times[i-1] + times[i]) * (diffs[i] - level); // 추가 시간 계산
            }
            curTime += times[i]; // 각 구간의 기본 시간을 더합니다.
        }
        
        // 계산한 총 시간이 제한을 넘는지 확인합니다.
        return curTime > limit;
    }
    
    // 난이도의 최댓값을 반환하는 메서드입니다.
    public long getMaxLevel(int[] diffs) {
        long result = 0;
        
        // 모든 난이도를 순회하며 최댓값을 찾습니다.
        for (int i = 0; i < diffs.length; i++) {
            result = Math.max(result, diffs[i]);
        }
        
        return result;
    }
}