징검다리 건너기

문제 정보

• 프로그래머스 Lv.3
• 이진 탐색
• 문제 링크

풀이

이진 탐색

이진 탐색을 활용해 풀 수 있다.

문제를 “건너뛸 수 있는 최대 칸 수가 $k$일 때, $m$명은 징검다리를 건널 수 있는가?”로 바꿔 생각하는 것이다. (파라메트릭 서치)

이 경우 시간복잡도는 $O(n\log m)$이 된다. (여기서 $n$은 stones.length, $m$은 max(stones[i]))

슬라이딩 윈도우

슬라이딩 윈도우를 활용하면 $O(n)$만에 푸는 것도 가능하다.

연속된 0의 개수 $\ge k$이면 그 이상 징검다리를 건너는 게 불가능하다.

길이가 $k$인 구간에서의 최대값이 그 구간을 건널 수 있는 사람의 수가 된다.

이걸 stones[] 전체로 확장하면, 답은 길이가 $k$인 모든 구간의 최대값 중 최소값이다.

코드

이진 탐색

class Solution {
    public int solution(int[] stones, int k) {        
        int low = 1;
        int high = 200_000_000;
        
        while (low <= high) {
            int mid = (low + high) / 2;
            
            if (isPossible(mid, stones, k))
                low = mid + 1;
            else
                high = mid - 1;
        }
        
        return high;
    }
    
    private boolean isPossible(int num, int[] stones, int k) {
        int cnt = 0;
        
        for (int stone : stones) {
            if (stone - num < 0)
                cnt++;
            else
                cnt = 0;
            
            if (cnt == k)
                return false;
        }
        
        return true;
    }
}

슬라이딩 윈도우

import java.util.*;
 
class Solution {
    public int solution(int[] stones, int k) {
        int answer = Integer.MAX_VALUE;
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < stones.length; i++) {
            while (!deque.isEmpty() && stones[deque.peekLast()] <= stones[i])
                deque.pollLast();
            
            deque.addLast(i);
 
            if (deque.peekFirst() <= i - k)
                deque.pollFirst();
            
            if (i >= k - 1)
                answer = Math.min(answer, stones[deque.peekFirst()]);
        }
        
        return answer;
    }
}