[Programmers] 징검다리 건너기 (Java)

문제 링크

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

문제

문제를 읽어보면 구해야하는 값은 파악할 수 있다.
k개만큼 건너 뛸 수 있다. 즉 만약 k길이의 다리를 건넌다고 가정했을 때 k개의 디딤돌 중 가장 큰 수만큼의 인원이 다리를 건널 수 있다.

ex) k = 3, stones = {2, 100, 2} -> answer = 100

첫번째 접근

처음에는 이중 반복문을 이용해서 i번째 지점부터 i+k지점까지 중 가장 큰 디딤돌의 수 localMax를 구하고, 모든 연속된 k길이의 구간에서 localMax 중 가장 작은 값은 정답으로 설정하고 코드를 작성하였다.
-> 효율성 테스트 실패

1<= k<=stones.length<=200000 이고 최악의 경우 O(N^2)의 시간복잡도를 가지는 풀이이므로 실패했다.

두번째 접근

이전에 c++로 푼 적이 있는 문제였고 해당 풀이를 참고하여 이분탐색 알고리즘을 이용하는 문제라는 것을 알았다.

이분탐색을 이용해 임의로 건널 수 있는 인원수를 가정하고, 해당 인원수만큼 건널 수 있는지 확인하는 과정을 통해 실제 정답의 범위를 좁혀나가는 원리이다.

이분탐색은 정렬된 집합에서 사용해야 하는 게 아닌가라고 생각했는데 이런 식으로 정답을 임의로 가정하고 범위를 좁혀나가는 방식으로도 사용할 수 있다는 점을 상기할 수 있었다.

코드

class Solution {
    public int solution(int[] stones, int k) {
       
        int l = 0;
        int r = 200000000;
        int m = (l+r)/2;
        int answer = 0;
        
        while(l<=r){
            int limit = 1;
            boolean success = true;
            for(int i=0; i<stones.length; i++){
                if(stones[i] < m&& limit < k){
                    limit++;
                }
                else if(stones[i]>=m){
                    limit = 1;
                }
                else {
                    success = false;
                    break;
                }
            }
            if(success){
                answer = m;
                l = m+1;
                m = (l+r)/2;
            }
            else{
                r = m-1;
                m = (l+r)/2;
            }
        }
        
        return answer;
    }
}

자바 언어에 익숙해지기 위해서 코딩테스트 문제를 자바로 풀어볼 생각이다.