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

요즘 코딩 테스트를 보면 `이분탐색`과 `완전탐색`이 정말 많이 나오는 것 같다.

그래서, 알고리즘 스터디에서 `이분탐색` 주에도 열심히 문제를 풀었고 혼자서도 많은 `이분탐색`문제를 접해보았다.

 

그러다가 요번에 프로그래머스에서 새롭게 나온 PCCP 문제를 접근했는데

 

와 이건 이분탐색 문제다 라고 바로 생각이 났다.

 

이전까지는 이분탐색 문제를 보면 그리디라고 생각이 들었는데 이제는 조금 감이 생긴 것 같다.

 

 

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

 

프로그래머스

 

 

문제 설명을 읽어보면 숙련도의 최소값을 찾는 것이다.

 

뭐 문제 설명은 어렵게 되어있지만, 사실 잘 읽어보면 친절하다.

 

그냥 숙련도 계산은 이렇게 하면 되는데 최소값을 찾아야 해 근데 값이 엄청나게 클 수도 있어

그럼 반복문으로 풀면 시간초과가 나겠지?

 

위와 같다는 느낌을 받았다. 그래서 이건 이분탐색이다. 라고 생각하여 접근했고 작성한 코드는 아래와 같다.

 

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int N = diffs.length;
        
        int max = 0;
        
        for(int diff : diffs){
            max = Math.max(diff, max);
        }
        
        int left = 1;
        int right = max;
        
        while(left <= right){
            int mid = (left + right) / 2;
            
            long sum = 0;
            
            for(int i = 0; i < N; i++){
                if(diffs[i] <= mid){
                    sum += times[i];
                } else{
                    if(i == 0){
                        sum = limit++;
                        break;
                    }
                    sum += ((times[i] + times[i - 1]) * (diffs[i] - mid)) + times[i];
                }
            }
            
            // System.out.println("left: " + left + ", right: " + right + ", mid: " + mid + ", sum: " + sum);
            if(sum <= limit){
                right = mid - 1;
            } else{
                left = mid + 1;
            }
        }
        
        return left;
    }
}