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

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

 

문제 파악

문제 설명

주어진 변수

문제 자체는 이해가 어렵지 않았다. 최초(=최소)로 퍼즐을 다 풀 수 있는 숙련도를 찾도록 하자.

아래 조건을 잘 이해하면 구현은 어렵지 않았다.

- diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
- diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.

또한 첫 번째 난이도의(diff[0]) 값은 고정으로 1로 주어지기 때문에 예외 처리는 조금 수월했다. 

어려운 점

채점시 3개가량 타임아웃이 발생해서 호출부에서 이진탐색으로 최소 숙련도를 찾도록 수정하였다.

풀이

변수를 어느 정도 종합해 볼까도 생각했는데
time_cur, time_prev와 같이 이전 인덱스의 시간이 필요해 순차적으로 배열 순회는 필요하다고 판단했다.

최대한 for문 내에서 조건을 만족하지 못하면 빠져나올 수 있도록 구현하였다.

코드

public class L340212 {
    
    public int solution(int[] diffs, int[] times, long limit) {
        int min = 1;
        int max = Arrays.stream(diffs).max().orElse(1);
        while (min < max) {
            int mid = (min + max) / 2;
            if (isLevelReachable(mid, limit, diffs, times)) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
    
    private boolean isLevelReachable(int level, long limit, int[] diffs, int[] times) {
        for (int i = 0; i < diffs.length && limit >= 0; i++) {
            long toUse;
            if (diffs[i] <= level) {
                toUse = times[i];
            } else {
                toUse = (long) (diffs[i] - level) * (times[i] + times[i - 1]) + times[i];
            }
            limit -= toUse;
        }
        return limit >= 0;
    }
}