[프로그래머스] 퍼즐 게임 챌린지(JAVA)

문제

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

---

풀이(21분)

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = Integer.MAX_VALUE;
        int left = 0;
        int right = Integer.MAX_VALUE;
        int level;
        while (left <= right) {
            level = (left + right) / 2;
            long totalTime = 0;
            long timeSum = 0;
            for (int i = 0; i < diffs.length; i++) {
                if (i > 0) {
                    timeSum = times[i - 1];
                }
                if (level >= diffs[i]) { // 바로 해결할 수 있다면
                    totalTime += times[i];
                    continue;
                }
                long time_prev = (timeSum + times[i]) * (long) (diffs[i] - level) + times[i];
                totalTime += time_prev;
            }
            if (totalTime <= limit) {
                if(level >= 1){
                    answer = level;
                }
                right = level - 1;
            } else {
                left = level + 1;
            }
        }
        return answer;
    }
}

 

가벼운 이분탐색 문제라고 생각했다. 최대 레벨과 최소 레벨을 설정한 뒤 해결 가능하다면 더욱 낮은 레벨을 할 수 있는 방법은 없는지 탐색하는 것이다.

 

1. level의 중간값을 구한다. (초기 0과 int최댓값의 중간값이 된다.)

2. 해당 레벨일 떄의 문제 해결 시간을 구한다.

3 - 1. 걸린 시간이 limit보다 작았다면 레벨을 낮추기 위한 작업을 한다. --> right를 level(이분 탐색의 mid) -1 로

3 - 1 - 1 이 과정에서 정답은 최소 1 이상이게 셋팅한다.

3 - 2. 걸린 시간이 limit 보다 크다면 레벨을 높인다. --> left를 level(이분 탐색의 mid) + 1로