프로그래머스 - 퍼즐 게임 챌린지

문제 링크 ▶︎ 퍼즐 게임 챌린지

문제 파악

문제에서 diffs, times의 길이가 30만이고 diffs의 값도 10만이기 때문에 순차적으로 레벨을 ++하거나 --해서 완전탐색해서는 시간초과를 뚫을 수가 없다. 그래서 이분법으로 접근한다면 레벨은 diffs의 min과 max 사이에서 움직일 것이므로 시간초과를 해결할 수 있다.

접근 방법

1. diffs의 배열에서 min값은 항상 1이다. 그리고 max값을 구해서 각각 left와 right에 넣어둔다.

2. 그 중앙값으로 level을 설정하고 소요되는 전체 시간을 측정하고 만약 소요 시간이 limit보다 작거나 같다면 레벨을 낮춰볼만하기 때문에 right를 현재로 바꾸고 다시 설정한다.

3. 소요시간이 limit보다 크다면 레벨을 높여야하기 때문에 left를 현재로 바꿔서 계속 진행한다.

4. 그러다가 left가 현재와 같아진다면, 즉 한계 left만큼 갔는데 더 낮아질 여지를 찾는다는 것이므로 해당 값이 퍼즐을 해결할 수 없는 최댓값이라는 의미고 해당 값에 +1 한것이 정답이 된다. 반면에 left와 now가 모두 1이라는 것은 레벨에 상관없이 무조건 퍼즐을 해결한다는 뜻이므로 1을 리턴한다.

코드 구현

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int len = diffs.length;
        int left = 1;
        int right = 1;
        for (int diff : diffs) {
            if (diff > right) {
                right = diff;
            }
        }
        int now = (left + right) / 2;
        while (true) {
            long cnt = 0;
            for (int i=0; i<len; i++) {
                if (diffs[i] <= now) {
                    cnt += times[i];
                } else {
                    cnt += ((times[i-1] + times[i]) * (diffs[i] - now));
                    cnt += times[i];
                }
            }
            if (cnt <= limit) {
                right = now;
                now = (left + right) / 2;
            } else {
                left = now;
                now = (left + right) / 2;
            }
            if (left == now) {
                now++;
                break;
            }
        }
        if (left == 1) {
            now = 1;
        }
        return now;
    }

}

개선 사항

개념에 따라서 수행되지만 left가 1일때, 즉 레벨에 관계없이 모든 퍼즐이 수행된다는 것을 찾는 과정이 어려웠다.