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

문제

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

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

 

접근법

효율성 문제였기 때문에 이분탐색으로 풀 생각 먼저 했다.

배열의 가장 작은 값과 가장 큰 값을 구하고

그 사이의 값을 이분탐색하면서 답이 될 수 있는 값 중에 가장 큰 값을 찾았다.

 

코드

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;

        int min = getMin(stones);
        int max = getMax(stones);

        while(min <= max){
            int mid = (min+max) / 2;
            
            if(isPossible(stones, mid, k)) {
                answer = Math.max(mid, answer);
                min = mid+1;
            }else{
                max = mid-1;
            }
        }
        return answer;
    }

    private boolean isPossible(int[] stones, int mid, int k) {
        int cnt = 0;
        
        for(int stone : stones){
            if(stone >= mid){
                cnt = 0;
            //건널 수 없으면 카운트    
            }else{
                cnt++;
            }
            //건널 수 없는 돌의 연속된 개수가 k와 같아지면 불가능
            if(cnt==k) {
                return false;
            }
        }
        return true;
    }

    private int getMin(int[] stones) {
        int min = Integer.MAX_VALUE;
        for(int stone : stones)
            min = Math.min(stone, min);

        return min;
    }

    private int getMax(int[] stones) {
        int max = Integer.MIN_VALUE;
        for(int stone : stones)
            max = Math.max(stone, max);

        return max;
    }
}