PGMRS_퍼즐 게임 챌린지(PCCP 기출, JAVA)

 

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

프로그래머스

 

이 문제는 사실 단순하게 풀려면 아래와 같은 풀이로도 가능한데

class Solution {
    static int[] diffs, times;
    static long limit;
    
    public int solution(int[] diffs, int[] times, long limit) {
        // 할당
        this.diffs = diffs;
        this.times = times;
        this.limit = limit;
        
        int i = 0;
        while(true){
            i++;
            boolean valid = solving(i);
            if(valid) break;
        }
        
        return i;
    }
    
    public boolean solving(int level){
        // 제한 시간 내 가능 여부를 리턴한다.
        long spend = 0L;
        for(int i = 0; i<diffs.length; i++){
            if(level >= diffs[i]) {
                spend += times[i];
                continue;
            }
            
            // diffs[0] = 1임이 보장되어 있고, level은 양의 정수여야 하므로
            // i == 0에서의 시행은 무조건 위 if condition을 만족한다.
            // 따라서, 아래 diffs[i-1] 연산에서 i == 0인 경우(ArrayOutOfBoundsException)에 대한 케어는 진행하지 않는다.
            // 이를 응용하여, 반복문을 i = 1부터 시작해도 좋다.
            
            spend += (times[i] + times[i-1]) * (diffs[i] - level);
            spend += times[i];
            if(limit < spend) return false; // TC 3번은 왜 여기서 못 걸러내나?
        }
        if(limit < spend) return false;   
       // System.out.printf("Whoo! %d\n", spend); // TC 3번은 위 조건문이 없으면 1724가 나온다!
        return true;
    }
}

이 코드는 level(숙련도)의 최솟값을 구하는 문제이니, 0부터 최솟값을 하나하나 증가시키며 테스트한다.

'최솟값'이니까, 0부터 시작하면 되겠지? 고 풀면 이렇게 된다. 그런데,

이렇게 풀면 틀린다. 왜?

 

?

'최솟값'이 아득하게 큰 경우가 있기 때문이다. limit을 long으로 줄 때부터 눈치를 까야 됨(하지만 나는 틀리고서야 알았지 ㅋㅋ)

나는 단순히 0부터 시작하렴 ~ 하고 걸어 놨기 때문에

최솟값부터가 엄청 큰 경우 답이 없어진다.

 

그래서 이건 이분 탐색 문제가 된다. 

 

풀이의 방향을 이분 탐색으로 정하고 나면, 바로 다음으로 생각할 거리가 생기는데

탐색 범위가 어디부터 어디까지인가? 하는 것이다.

나는 solving(int level)을 가지고 탐색 중이기 때문에

이 경우 level의 구간이 탐색 범위가 된다. 

그렇다면 level의 구간은 어디부터 어디까지인가? 

쏘 간단쓰 .. 1 ~ max(diff)가 되겠음 왜냐 

level >= diff[i]이기만 하면 time[i]에 퍼즐을 풀 수 있다 따라서

diff의 최댓값보다 level이 높은 것은 소용이 없음이다.

 

그러면 diff의 최댓값을 구해야 하는데 이거를 굳이 ... 두 개 세 개 골라 찝어가며 비교하지 말고 

O(N)으로 배열 순회하면서 int max 값 갱신하면 됨

쉬운 로직인데 왜 굳이 글로 쓰냐면 진짜 ..... 혹시나 그런 일은 없겠지만 .... 까먹지 말라고 ....................... ㅎㅎ

 

https://nogotit.tistory.com/entry/BOJ1920-%EC%88%98-%EC%B0%BE%EA%B8%B0JAVA

BOJ_1920 수 찾기(JAVA)

이걸 참고해서, 위 코드를 이분탐색 로직으로 바꾸어 보자. 

class Solution {
    static int[] diffs, times;
    static long limit;
    
    public int solution(int[] diffs, int[] times, long limit) {
        // 할당
        this.diffs = diffs;
        this.times = times;
        this.limit = limit;
        
        // 이분탐색 포인터 정하기
        int start, end, mid;
        start = 1; // ! 
        end = 0;
        int result = Integer.MAX_VALUE;
        
        for(int i : diffs){
            if(i>end) end = i;
        } // 초기 end값 세팅(탐색할 level의 상한선)
        
        while(start <= end){
            mid = (start + end) / 2;
            if(solving(mid)) {
                // 최솟값을 찾는 것이므로 탐색 범위를 아래로 내려야 한다.
                if(result > mid) result = mid;
                end = mid - 1;
                continue;
            }
            
            start = mid + 1;
        }
        
        return result;
    }
    
    public boolean solving(int level){
        // 제한 시간 내 가능 여부를 리턴한다.
        long spend = 0L;
        for(int i = 0; i<diffs.length; i++){
            if(level >= diffs[i]) {
                spend += times[i];
                continue;
            }

            spend += (times[i] + times[i-1]) * (diffs[i] - level);
            spend += times[i];
            if(limit < spend) return false; 
        }
        
        if(limit < spend) return false;   
        return true;
    }
}

start의 초기값이 왜 1이냐면 ..... 이게 0이면 틀리는 케이스가 있다(정확히는 ArrayIndexOutOfBoundsException이 발생함(-1을 탐색, 즉 level=0일 때))

어차피 start는 level이 가질 수 있는 범위의 최소 값이고 .... level은 무조건 양의 정수라고 문제에서 명시하고 있기 때문에, 1을 지정해 주면 된다. 

 

이분탐색을 활용해야 모든 케이스를 통과할 수 있다.