프로그래머스 징검다리 건너기 (이분탐색, java)

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

범위가 커서 이분탐색으로 풀어야 한다. 

1. 징검다리 돌 중에 제일 큰 값을 찾아 건널수 있는 동물 수의 상한선으로 두고
2. 이분탐색으로 건널수 있는 동물 수를 찾는다
3. 2번에서의 조건은 'stone - animal <0 가 k번 이상 연속되면 안된다' 이다. 
--> 0인 돌이 2개면 3번 점프해서 건너야 한다. 

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        int lo = 1;
        int hi = Arrays.stream(stones).max().getAsInt();
        int mid = 0;
        while(lo<=hi){
            mid = (lo+hi)/2;
            if(!isPossible(mid, k, stones)){// 불가능하면 줄여야됨
                hi = mid-1;
            }else{// 가능하면 늘리기
                answer = mid;
                lo = mid+1;
            }
        }
        return answer;
    }
    public boolean isPossible(int animal, int jump, int[] stones){
        // jump가 3이면 0미만인 돌이 2게를 초과하면 즉 3개 이상이면 불가능함
        // jump = 3이면 cnt==jump일때 return false
        int cnt=0;
        for(int i=0; i<stones.length; i++){
            if(stones[i]-animal < 0){
                cnt++;
                if(cnt>=jump) return false;//
            }
            else cnt = 0;
        }
        return true;
    }
}

 

 

이분탐색은 매번 범위를 절반으로 줄여가며 탐색해서 순차탐색시 O(N^2) 걸리던 것을 O(logN) 시간복잡도를 가지게 한다. 

이분탐색시 구하려는 값에 따라서 조금씩 변화를 줘야 하는데 헷갈려서 검색하던 중 다음과 같은 글을 발견..

이분 탐색(Binary Search) 헷갈리지 않게 구현하기