[Java] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

처음에는 뭔 말이야? 했지만

읽다보니까, 결국 문제에서 원하는 건 간단했다.

문제의 조건을 충족하면서 + limit 안에 + 모든 diffs를 풀 수 있게 하는 

=> level 을 구하시오!

 

여기서 고민이 되었다.

1부터 제한 범위까지 완탐을 하는 건 시간 초과가 날 것 같은데,

완탐은 아니면서 범위내에서 유동적으로 어떻게 level을 구해야하나 싶었다.

범위 내에서 유동적으로...

범위 내에서 유동적으로...

이렇게 생각하다보니 어느 특정값 하나를 구하고,

그 값을 기준으로 요리조리 움직이다 보면 완탐보다는 나을 것 같은데? 라는 생각이 들었다.

 

그럼 여기서 또 고민..ㅎ

그 특정값을 무슨 기준으로 구할까?

처음에는 time 배열을 기준으로 봐야하나 싶었다가, 시간을 계산하는 주요 포인트가 diffs라고 생각했다.

그리고 아래처럼 중간값을 구하고자 했다.

 

1. diffs의 모든 합 / diffs.length() 

2. diffs의 최댓값 / 2

위의 선택지 중, 나는 2의 선택지로 초기 레벨을 설정했고

이 레벨의 값을 조정해나가며 최소 level을 구하는 로직을 설계했다.

• limit 이하 -> middle_level을 -1
• limit 초과 -> middle_level을 +1
• diffs[i] <= middle_level 일 경우, total_time += time[i]
• diffs[i] > middle_level 일 경우, total_time += (diffs[i]-middle_level)*(times[i]+times[i-1]) + times[i]

 

[초기 풀이] - 오답

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int sum = 0;
        for(int dif : diffs){
            sum += dif;
        }
        int middle_level = sum/diffs.length;
        
        
        long total_time = calculateTime(middle_level, diffs, times);
        if(total_time <= limit){
            while(total_time <= limit){
                answer = middle_level;
                total_time = calculateTime(--middle_level, diffs, times);  
            }
        }else{
            while(total_time > limit){
                answer = middle_level;
                total_time = calculateTime(++middle_level, diffs, times);  
            }
        }
    
        return answer;
    }
    
    long calculateTime(int middle_level, int[] diffs, int[] times){
        long time = 0; 
        for(int i = 0; i < diffs.length; i++){
            if(diffs[i] <= middle_level) time += times[i];
            else{
                time += (diffs[i]-middle_level)*(times[i]+times[i-1]) + times[i];
            }
        }
        return time;
    }
}

그렇지만 이렇게 풀었을 때 테스트케이스의 3번을 통과하지 못했다. 
계속 293이 나와서 어디가 문제인지 찾아봤는데 solution()에서 if-else 부문에서 문제가 발생한 것 같았다.

제한시간 1시간내 풀기에 실패해서

결국 피티-지에게 도움을 요청했는데, 내 코드를 보자마자 "이진탐색" 이라는 키워드를 말하는게 아닌가!!!

이진탐색..? 이..진탐...색!!!

이러면서 나도 이진탐색으로 solution()에서 level을 측정하는 로직을 수정했다.

나는 초기의 level을 모든 diffs의 합을 diffs의 길이로 나눠 구했지만,

이진탐색으로는 1과 최대 diffs 값을 이용하여 구했다.

그렇게 하다보니 이전보다 훨씬 로직이 간단해졌고, 결과는 통과!!

 

[정답 풀이]

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int start = 1;
        int end = Arrays.stream(diffs).max().getAsInt();
        
        while(start <= end){
            int level = (start+end)/2;
            long total_time = calculateTime(level, diffs, times);
            
            if(total_time <= limit){
                answer = level;
                end = level-1;
            }else{
                start = level+1;
            }
        }
        
    
        return answer;
    }
    
    long calculateTime(int middle_level, int[] diffs, int[] times){
        long time = 0; 
        for(int i = 0; i < diffs.length; i++){
            if(diffs[i] <= middle_level) time += times[i];
            else{
                time += (diffs[i]-middle_level)*(times[i]+times[i-1]) + times[i];
            }
        }
        return time;
    }
    
}​