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

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

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

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

풀이

이분탐색 문제이다! 이분탐색을 하지 않고 풀면 시간초과가 날 것이다!

 

전형적인 이분탐색의 유형으로 최소값, 최대값을 건널 수 있는 프렌즈의 수 범위로 둔다. 처음에는 min을 0, max를 건널 수 있는 프렌즈의 최대값으로 둔 다음, mid이상의 프렌즈가 건널 수 있다면 min을 mid + 1로, mid이상의 프렌즈가 건널 수 없다면 max를 mid - 1로 변경하여 또 탐색한다.

 

이때 건널 수 있는지 없는지 판단하는 방법은 간단하다. stones의 각 요소가 mid보다 작은지만 판단하면 된다. 그리고 작을때는 count변수를 사용해 작은 stones의 연속적인 개수를 세어주고 count가 k와 크거나 같아지는 순간 건널 수 없는 상태가 된다.

 

코드

class Solution {
   public int solution(int[] stones, int k) {
        int min = 0;
        int max = Integer.MAX_VALUE;
        int result = 0;
        while(min <= max) {
            int mid = (min + max) / 2;
            if(check(mid, k, stones)) {
                min = mid + 1;
                result = mid;
            } else {
                max = mid - 1;
            }
        }
        return result;
    }
    
    public boolean check(int mid, int k, int[] stones) {
        int count = 0;
        for(int i = 0; i < stones.length; i++) {
            if(stones[i] < mid) { //mid보다 작으면 mid가 건널 수 없다.
                count++;
                if(count >= k) return false;
            } else count = 0;
        }
        return true;
    }
}