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

문제 설명

• https://www.acmicpc.net/problem/28707
• LV 2

문제 풀이

• 이분 탐색을 사용하였다.
• 0~10만까지 범위의 level 내에서 각 level이 valid한지를 판별하는 함수를 통해 이분탐색을 진행하면 풀이가 가능하다.

소스 코드 (JAVA)

class Solution {
    long L;
    int[] D, T;
    int N; 
    
    // 해당 level값이 제한 시간을 만족하는지 여부 
    public boolean isValid(int level) {
        long sum = 0L;
        
        //각 문제별 소요시간을 모두 더해줌 
        for (int i = 0; i < N; i++) {
            int diff = D[i] - level;
            sum += (long)T[i];
            
            // 틀리는 경우에 
            if (diff > 0) {
                long tmpSum = 0L;
                tmpSum += (T[i] * diff);
                if (i != 0) tmpSum += (T[i-1] * diff);
                sum += tmpSum;
            }
        }
        if (sum > L) return false;
        else return true;
    }
    
    public int solution(int[] diffs, int[] times, long limit) {
        D = diffs;
        T = times;
        L = limit;
        N = diffs.length;
        
        int lo = 0;
        int hi = 100001;
        while(lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            if (isValid(mid)) hi = mid;
            else lo = mid;
        }
        return hi;
    }
}