[Programmers] 퍼즐게임(Java)

이번에는 프로그래머스에서 퍼즐게임 문제를 풀어보았습니다.

2레벨 문제 중 정답률(41%) 하위권 문제였는데 지문이 얼핏보면 상당히 복잡해보였습니다. 제가 이해할때는 약간 RPG 게임상 필드 몬드터를 떠올렸는데 내 레벨이 몬스터보다 높으면 한방컷이고 낮으면 여러방을 때려야하는 그런 느낌으로 보니 금방 이해 된 것 같습니다.

조건을 간단하게 요약이 불가능한 문제여서 정확한 문제설명은 퍼즐게임 문제 자체를 읽는 것이 좋습니다.

일단 처음에 입출력 예시를 보고 '너무 쉬운데??' 라고 생각했는데 역시나 시간 초과가 나오더군요. 문제는 LEVEL을 1씩 증가시켜서 순차적으로 검색하는 것이 문제였습니다. 그래서 MAX LEVEL을 주어진 DIFF 배열(LEVEL 배열) 중 가장 높은 값으로 잡고 시작점을 0으로 잡고 이진 탐색을 수행하니 대부분 풀렸습니다.

그러나 테스트 14번에서 자꾸 시간 초과가 나오길레 이것 저것 만지다가 LEFT 값을 1로 하니 성공했습니다. LEFT 값이 0이던 1이던 속도 차이는 거의 없는 걸로 알고있는데.. 이것을 의도한건지 안한건지는 모르겠습니다.

프로그래머스가 의도 한 것은 탐색알고리즘을 이용한 LEVEL 검색 및 효율적인 소요시간 계산 로직 정도를 의도한 것 같고 0과 1 관련해서는 제가 발견 못하거나 이해 못한 것일 수 있지만 일단은 프로그래머스 오류로 생각됩니다.

[전체코드]

public class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int maxDiff = 0;
        for (int diff : diffs) { // 레벨 중 가장 큰 값을 MAX 값으로 설정
            maxDiff = Math.max(maxDiff, diff);
        }

        int left = 1;
        int right = maxDiff;
        int answer = maxDiff;

        while (left <= right) { // 이진탐색
            int mid = left + (right - left) / 2; // 중간을 기준으로
            long timeTaken = calculateTimeTaken(diffs, times, mid, limit);

            if (timeTaken <= limit) {
                answer = mid;
                right = mid - 1; // 소요시간이 더 작은 값이 존재하는지 확인 
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }

    private static long calculateTimeTaken(int[] diffs, int[] times, int level, long limit) {
        long timeTaken = 0;
        int prevTime = 0;

        for (int i = 0; i < diffs.length; i++) {
            if (level >= diffs[i]) {
                timeTaken += times[i];
            } else {
                timeTaken += (long)(times[i] + prevTime) * (diffs[i] - level) + times[i];
            }

            if (timeTaken > limit) {
                return timeTaken;
            }

            prevTime = times[i];
        }
        return timeTaken;
    }
}