[JAVA] 프로그래머스 [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

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

프로그래머스

코딩테스트 연습 > PCCP 기출문제 > [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

 

문제 분석

난이도: LEVEL2 

문제유형: 이분탐색(매개변수 탐색)

 

문제 요구사항 요약

주어지는 제한시간 안에서 최소한의 숙련도(LEVEL)을 통해 모든 퍼즐문제를 해결하고 싶다.

지정한 숙련도가 문제의 난이도 보다 크거나 같으면 정해진 시간을 투자하면 끝이지만

지정한 숙련도가 문제의 난이도 보다 낮으면 (문제의 난이도 - 숙련도) = N

N번 만큼 (이전 퍼즐의 문제 해결 시간 + 이번 퍼즐의 문제 해결 시간)이 추가로 든다. 

즉 이번 문제 번호가 i라고 하면 (diffs[i] - level(지정한 숙련도)) * (times[i-1] + times[i]) + times[i] 식이 나온다.    

 

추가로 이런 케이스를 고려해야한다. 

첫 번째 문제에서는 이전 퍼즐의 문제 해결 시간이란 개념이 없다 

첫 번째 문제에서 지정한 숙련도 보다 문제의 난이도가 더 높으면 구해놓은 식에서 이전 퍼즐의 문제 해결 시간을 0으로 잡으면 된다. 

또한 지정할 수 있는 숙련도는 1 이상이다.  최솟값이 1이라는 뜻이다. 

 

정답 코드 

import java.util.*;
class Solution {
    static int [] diffss;
    static int [] timess;
    static long limits;
    static int size;
    public long solution(int[] diffs, int[] times, long limit) {
        // static 변수 초기화 
        diffss = diffs; // 난이도 
        timess = times; // 소요 시간 
        limits = limit; // 제한 시간 
        size = diffs.length; 
        
        long end   = Long.MAX_VALUE;
        long start = 0;
        // 이분 탐색 시작 
        while(start < end){
            long mid = (start + end) / 2;
            long result = calculate(mid);
        
            if(result > limit){
                start = mid + 1;
            }
            else end = mid;
        }
        return start;
    }
    public long calculate(long level){
        if(level <= 0){ // level은 항상 0보다 크다 
            return Long.MAX_VALUE;
        }
        long use = 0; // 해당 숙련도로 소요하는 시간 
        for(int i = 0; i < size; i++){
            if(diffss[i] <= level){
                use += timess[i];
            }
            else{
                long count = diffss[i] - level;
                if(i == 0){
                    use += timess[i] * count + timess[i];
                }
                else{
                    use += (timess[i] + timess[i-1] ) * count + timess[i];
                }
            }
            if(use > limits){ // 이미 제한 시간을 넘겼다면 더 계산할 필요 x
                return use;
            }
        }
        return use;
    }
}