[프로그래머스] 2019 카카오 겨울인턴. 징검다리 건너기 (Java)

Problem

• 문제 링크

징검다리를 건널 수 있는 프렌즈 인원수를 구하는 문제입니다.

징검다리는 stones 배열로 주어지며, 한번 발을 디딜때마다 1 씩 줄어듭니다.

프렌즈들은 0 인 돌을 만나면 최대 k 만큼 가장 가까운 돌로 점프할 수 있습니다.

Solution

이분탐색을 응용한 파라메트릭 서치(Parametric Search) 를 활용하는 문제입니다.

건널 수 있는 프렌즈들의 최대, 최소값은 stones 배열의 최대, 최소값과 동일합니다.

stones 배열의 최대값이 5, 최소값이 1 이라고 할 때 1 과 5 로 이진탐색을 돌립니다.

중간값 mid 가 3 이기 때문에 프렌즈 인원을 3 으로 정해두고 전부 다 건널 수 있는지 탐색합니다.

만약 다 건널 수 있다면 3 보다 작은 1, 2 도 전부 건널 수 있기 때문에 3 ~ 5 사이의 값을 탐색합니다.

이런식으로 건널 수 있는 프렌즈 인원 중 가장 큰 값이 남을때까지 계속 하면 됩니다.

건널 수 있는지 판단하는 canCross 함수는 돌에서 프렌즈 값을 뺀 숫자를 갖고 음수가 최대 k 만큼 연속하지 않은지 확인하면 됩니다.

Java Code

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        
        for (int stone : stones) {
            max = Math.max(max, stone);
            min = Math.min(min, stone);
        }
        
        return binarySearch(stones, k, min, max);
    }
    
    private int binarySearch(int[] stones, int k, int lo, int hi) {
        if (hi == lo) return lo;
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (canCross(stones, k, mid)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return lo - 1;
    }
    
    private boolean canCross(int[] stones, int k, int friends) {
        int passCount = 0;
        
        for (int stone : stones) {
            if (stone - friends < 0) {
                passCount++;
            } else {
                passCount = 0;
            }
            
            if (passCount == k) return false;
        }
        
        return true;
    }
}