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

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

프로그래머스

---

풀이

1 ~ 300,000 사이의 최소 레벨을 구해야 하므로 완전 탐색시 시간 초과가 날 것 같아 이분탐색을 사용했다.

최소 레벨을 1 (난이도가 양의 정수라 했으므로 최소 레벨은 1 이상이어야 함), 최대 레벨을 30만으로 잡고 탐색했다.

최소 - 최대의 중간값을 구해 해당 레벨일 때 주어진 퍼즐을 모두 풀 수 있는 지 확인,

풀 수 있다면 현재 레벨이 높은 것이므로 최대 레벨을 낮추고, 아니라면 최소 레벨을 높이는 방식으로 풀었다.

---

Java 코드

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int minLev = 1;
        int maxLev = 100_000;
        int answer = maxLev;
        
        while (minLev < maxLev) {
            int midLev = (minLev + maxLev) / 2;

            if (isPossibleSolve(diffs, times, midLev, limit)) {
                maxLev = midLev;
                answer = Math.min(answer, midLev);
            }
            else {
                minLev = midLev + 1;
            }
        }
        return answer;
    }
    
    private boolean isPossibleSolve(int[] diffs, int[] times, int lev, long limit) {
        long totalTime = 0;
        int prevTime = 0;
        
        for (int i = 0; i < diffs.length; i++) {
            if (lev < diffs[i]) {
                totalTime += (long)(prevTime + times[i]) * (diffs[i] - lev);
            }
            
            totalTime += times[i];
            prevTime = times[i];
            
            if (limit < totalTime) return false;
        }
        return true;
    }
}