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

문제 요약

$n$개의 퍼즐을 정해진 제한 시간(limit) 내에 풀어야 합니다.
각 퍼즐은 난이도와 소요 시간이 다르며, 나의 숙련도(level)에 따라 문제를 푸는 방식과 시간이 달라집니다.

목표는 제한 시간을 지키면서 가질 수 있는 숙련도의 최솟값을 찾는 것입니다.

입출력 예시

입력:

• diffs: 퍼즐별 난이도 배열 (예: [1, 5, 3])
• times: 퍼즐별 소요 시간 배열 (예: [2, 4, 7])
• limit: 전체 제한 시간 (예: 30)

출력:

• 제한 시간을 넘지 않는 최소 숙련도 (int)

접근 방법

우선 문제를 보면 어떤 값을 구해야 하는지부터 확인했습니다.
제한 시간 내에 풀 수 있는 숙련도의 최솟값을 구하는 것이 이 문제의 목표입니다.
이 문제에서는 특정 숙련도일 때 얼마나 시간이 소요되는지 계산 공식을 구할 수 있습니다.

즉 임의의 숙련도를 대입해서 계산 공식으로 시간을 구하고 이것이 제한 시간보다 큰 값인지 비교하면서 숙련도의 최솟값을 구하는 것이 이 문제의 핵심이라고 볼 수 있습니다.

물론 기본적으로는 숙련도(level)를 1부터 1씩 증가시키면서 구하거나
최댓값에서 1씩 감소시키면서 처음 limit을 넘지 않는 숙련도를 찾는 브루트포스로 풀 수 있습니다.

하지만 저는 최적화를 하기 위해 이분 탐색을 활용해 해당 문제를 풀었습니다.
최솟값은 1로 고정,
최댓값은 diffs 배열의 가장 큰 수로 고정시키고 그 사이에서 이분 탐색을 수행하도록 했고
Lower Bound을 찾는 이분 탐색을 구현하여 간단하게 정답을 구할 수 있었습니다.

코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int end = 0;
        
        for (int diff : diffs) {
            end = Math.max(end, diff);
        }
        
        return bs(1, end, diffs, times, limit);
    }
    
    static int bs(int s, int e, int[] diffs, int[] times, long limit) {
        if (s >= e) return e;
        
        int m = (s + e) / 2;
        
        if (isPossible(diffs, times, limit, m)) return bs(s, m, diffs, times, limit);
        else return bs(m+1, e, diffs, times, limit);
    }
    
    static boolean isPossible (int[] diffs, int[] times, long limit, int level) {
        long total = 0;
        int time_prev = 0;
        
        for (int i = 0; i < diffs.length; i++) {
            int time_cur = times[i];
            long plus = (time_cur + time_prev) * (Math.max(diffs[i] - level, 0)) + time_cur;
            total += plus;
            time_prev = time_cur;
        }
               
        return total <= limit;
    }
}