[프로그래머스] 퍼즐게임첼린지 자바 이진탐색

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

프로그래머스

 

문제

/**
 *
 * @param diffs 난이도 모음
 * @param times time_cur 모음
 * @param limit 총 제한 시간.
 * @return limit안에 모든 퍼즐을 풀 수 있는 최소 level
 */

접근

diffs에서 최고 레벨을 구한 후 / 2씩 범위를 줄여가며 찾으면 좋겠다고 생각했다.
그러나 어떤 방식으로 diff / 2 한 후 +-로 조정해야 할지 갈피를 잡지 못했음.

public int solution(int[] diffs, int[] times, long limit) {
        int minLevel = 1;
        int maxLevel = 0;

        //모든 스테이지를 다 클리어 했을 때 총 소요시간이 limit와 근사한 값이 나오면 최소 레벨.
        //최고 스테이지 먼저 찾아봄
        for(int i = 0; i < diffs.length; i ++){
            maxLevel = Math.max(maxLevel, diffs[i]);
        }


        int test = maxLevel / 2;
        getMidClearLevel(diffs, times, limit, test);

        return minLevel;
    }

    public int getMidClearLevel(int[] diffs, int[] times, long limit, int level){
        long time_prev = 0;
        for(int i = 0; i < diffs.length; i ++){
            int diff = diffs[i];
            int time_cur = times[i];
            if(diff > level){
                time_prev += time_cur;
            } else {
                time_prev += (diff - level) * (time_prev + time_cur);
            }
        }

        if(time_prev > limit) getMidClearLevel(diffs, times, limit, level + 1);

        return level;
    }

2차시도

GPT의 도움으로 코드를 수정했다. 반복 처리를 하며 범위를 좁혀가는 방식이었다.
하지만 제출 후 14번 케이스의 계속적인 실패 발생

 public int solution2(int[] diffs, int[] times, long limit) {
        int left = 0; // 최소 난이도
        int right = 100000; // 최대 레벨 범위 (제한이 없으면 적당히 크게 잡기)

        int answer = -1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (canClearAll(diffs, times, mid, limit)) {
                answer = mid;
                right = mid - 1; // 더 낮은 레벨로 시도
            } else {
                left = mid + 1; // 더 높은 레벨로 올려야 함
            }
        }
        answer = answer == 0 ? 1 : answer;
        return answer;
    }

    private boolean canClearAll(int[] diffs, int[] times, int level, long limit) {
        long totalTime = 0;
        for (int i = 0; i < diffs.length; i++) {
            if (diffs[i] <= level) {
                totalTime += times[i];
            } else {
                int time_prev = i == 0 ? 0 : times[i - 1];
                long penalty =  Math.max(0L, (long) diffs[i] - level);
                totalTime += (penalty * (time_prev + times[i]) + times[i]);

            }

            // 시간 초과 방지
            if (totalTime > limit) {
                return false;
            }
        }

        return true;
    }

다른 사람의 답변 참고

https://jincchan.tistory.com/57

동일하게 14번케이스에서 문제가 발생한 사람들이 있었다.
그 중 제일 맘에든 케이스를 참고하였다.

public int solution3(int[] diffs, int[] times, long limit) {
        int maxValue = Arrays.stream(diffs).max().isPresent()? Arrays.stream(diffs).max().getAsInt() : 0;
        int minValue = 1;

        while (minValue < maxValue) {
            int level = (maxValue + minValue) / 2;
            long time = calTime(diffs, times, level);

            if(limit >= time) {
                maxValue = level;
            } else {
                minValue = level+1;
            }
        }
        return maxValue;
    }
    private long calTime(int[] diffs, int[] times, int level){
        long time = 0;
        for(int i = 0; i < diffs.length; i++){
            if(diffs[i] <= level){
                time += times[i];
            } else {
                int prev_time = i == 0 ? 0 : times[i -1];
                time += (long) (prev_time + times[i]) * (diffs[i] - level) + times[i];
            }
        }
        return time;
    }

차이 요약

	solution2	solution3
이진 탐색 범위	[0, 100000] 등 제한된 범위로 고정	min = 1, max = max(diffs)로 유동적
종료 조건	left <= right + answer == 0이면 1로 강제 설정	min < max, 반환값 maxValue 자체로 결정
패널티 적용	Math.max(0, diff - level)로 예외 처리	무조건 (diff - level) 사용 (단, level은 절대 작지 않음)
반환 결과 보정	answer == 0 → 1 처리	없음