알고리즘87 :: 프로그래머스_징검다리건너기

package programmers;
 
public class 징검다리건너기 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] stones = {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};
        int k = 3;
        
        int low = 1;
        int high = 200000001;
        int mid = 0;
        
        
        while(low<=high) {
            int count = 0;
            mid = (low + high)/2;
            for(int i=0; i<stones.length; i++) {
                if(stones[i] - mid <=0)
                    count++ ;
                else
                    count=0;
                if(count>=k) {
                    high = mid-1;
                    break;
                }
            }//
            if(count<k) {
                low = mid+1;
            }
        }
        System.out.println(low);
        
    }
 
}
 

이 문제는 https://cjh5414.github.io/binary-search/

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

https://ksdyoung.tistory.com/69

징검다리 건너기 프로그래머스(c++)

참고해서 해결했다. 

 

결과적으로 봤을 때는 

https://tech.kakao.com/2020/04/01/2019-internship-test/

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

 

내용에서 가이드라인이 제시되어 있다. 

범위가 1~200,000,000 이기 때문에 초기값을 설정하고 

mid = (시작+끝)/2 가 돌다리를 건널 수 있는 인원이다.

돌다리 개수(=k) 개가 0이 되는 연속된 개수를 파악한다. 

0이 연속된 개수가 k개를 넘게 되면 돌다리를 건널 수 없는 범위가 되기 때문에 끝을 mid-1로 변경하고 반대로 돌다리를 건널 수 있다면 mid+1 로 변경해서 최종적으로는 시작이 끝보다 커지면 최대의 인원이 돌다리를 건널 수 있게 되는 경우이다. 

 

이분탐색 문제를 오랜만에 봐서 감이 없었다. 하핳... 어렵네