2019 카카오 개발자 겨울 인턴쉽 - 징검다리 건너기(이분 탐색, 슬라이딩 윈도우) - Java 풀이

https://programmers.co.kr/learn/courses/30/lessons/64062

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

- 다리의 길이가 N = 20만이기 때문에 다리 길이에 대하여 한 번에 최대로 건널 수 있는 K 사이즈의 윈도우를 만들어서 O(N) 복잡도로 풀거나 혹은 모든 돌들의 원소값이 M = 1~2억 이므로 건너갈 수 있는 인원을 찾는 이분 탐색으로 접근하면 O(NlogM) 복잡도로 풀 수 있다.
최대한 사람들이 점프를 많이 해야 많은 사람들이 많이 건널 수 있다. 처음에는 1칸씩 뛰다가 돌이 0이 되면서 최대 K칸까지 점프할 수 있다. 따라서 이미 건널 사람을 정해놓고 이분탐색을 하므로 점프해야되는 연속된 칸의 개수가 최대 k미만이면서 최대한 많은 사람들이 건널 수 있는 수를 찾는다

- 슬라이딩 윈도우로 풀 수 있는 카카오 출제 문제 중에 광고 삽입이라는 문제가 있다. 이와 유사하게 풀 수 있다. 

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        int s = 1, e = (int)1e8 * 2;
        
        while(s <= e) {
            int mid = s + (e - s) / 2;
            int seq = 0, maxseq = 0;
            
            for(int n: stones) {
                if(n <= mid) ++seq;
                else {
                    maxseq = Math.max(maxseq, seq);
                    seq = 0;
                }
            }
            maxseq = Math.max(maxseq, seq);
            
            if(maxseq >= k) e = mid -1;
            else s = mid + 1;
        }
        
        return s;
    }
}