[프로그래머스] 징검다리 건너기 - Java

- 링크 : https://programmers.co.kr/learn/courses/30/lessons/64062?language=java 

코딩테스트 연습 - 징검다리 건너기

 

- 참고 링크 : https://kyu9341.github.io/algorithm/2020/05/08/programmers_64062/

프로그래머스 - 징검다리 건너기 - kwon | kwon's Blog

 

- 풀이

 : 이분 탐색, 파라 메트릭 서치를 이용했다.

 : 어떤 최대로 뛸 수 있는 값을 n이라고 한다면 이 n을 배열에서 모두 뺀 값을 비교 하면서 연속으로 0이하 인 값이 k 개 이상이면 뛸 수 있다. yes

 : k 개미만이라면 뛸 수 없다. no

 : 따라서 결정 문제이다.

결정 문제란?

 

결정 문제란?

예를 들어 x에 대하여 y로 나누어 떨어지는가? 를 물었을 때

yes or no로 결정될 수 있는 문제

 

- 답

class Solution {
    public int solution(int[] stones, int k) {
        int left = 0;
        int right = 200_000_000;
        int answer = right;
        // 건널 수 있다.
        // 다 뺀 후에 연속된 0 이하 숫자 사람이 k 이상이면 가능
        
        while (left <= right) {
            int mid = (left + right) / 2;
            int[] checkstones = new int[stones.length];
            int count = 0;
            boolean isPossible = false;
            for (int i=0; i < stones.length; i++) {
                checkstones[i] = stones[i] - mid;
                if (checkstones[i] <= 0) {
                    count++;
                } else {
                    count = 0;
                }
                
                if (count >= k) {
                    isPossible = true;
                    break;
                }
            }
            
            if (isPossible) {
                answer = Math.min(mid, answer);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return answer;
    }
}