[JAVA] 2019 카카오 개발자 겨울 인턴십 【징검다리 건너기】

---

일단 stones 배열의 크기가 200000개이므로, 이중 for문을 절대 사용하면 안된다.

 

따라서 배열의 원소값으로 이분 탐색을 해서 값을 찾아야 한다.

 

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]

 

예제 처럼 위와 같은 경우에서

 

전체 3을 감소하면

 

[-1 1 2 0 -1 -2 1 -1 2 -2] 가 되는데, 0이하인 원소가 3개 연속으로 존재하는 구간이 생기므로 답이 3이 되는것이다.

 

만약 2를 감소하면

 

[0 2 3 1 0 -1 2 0 3 -1] 이 되어 0이하인 원소가 3개 연속으로 존재하지 않기 때문에 다음 사람이 건너갈 수 있다.

 

따라서, 전체에 x를 감소시켰을 때, 0이하인 돌이 연속으로 k개 이상 존재하는 x값을 이분탐색으로 구하면 된다.

 

 

 

초기값을 left = stones 배열의 최솟값, right = stones 배열의 최댓값 으로 두고

 

mid = (left + right) / 2 값으로 전체 감소를 하고 0 이하의 연속된 돌이 존재하는지 확인한다.

 

만약 존재한다면 최솟값을 올려서 검사를 해보면 되고 , 존재하지 않으면 최댓값을 낮춰서 탐색을 한번 더 해보면 된다.

 

 

---

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {

        int left = Arrays.stream(stones).min().getAsInt();
        int right = Arrays.stream(stones).max().getAsInt();

        while (left < right) {
            int mid = (left + right) / 2;
            if (isPossible(mid, stones, k)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    boolean isPossible(int num, int[] stones, int k) {
        int possible = 0;
        for (int stone : stones) {
            if (stone - num <= 0) {
                possible++;
            } else {
                possible = 0;
            }
            if (possible == k) {
                return true;
            }
        }
        return false;
    }
}