징검다리 건너기

문제

프로그래머스

징검다리를 건널 수 있는 사람 숫자를 세는 문제이다.

예를 들어 징검다리인 stones = {2, 4, 5, 3, 2, 1, 4, 2, 5, 1} 이라고 한다면, 사람이 지나갈 때 마다 징검다리의 숫자는 -1씩 된다.

만약 징검 다리의 숫자가 0이 되면 점프해서 다음 징검다리로 건너가야 한다. 

최대 k개의 징검다리를 건너갈 수 있다면 몇명의 사람이 이용가능할 까?

예를 들어 k = 3이면 아래 예시와 같다.

 

처음에 접근할 때는 stones를 처음부터 k의 구간을 계속 보면서 확인하였다.

 

내 첫 코드

class Solution {
    public int solution(int[] stones, int k) {
        int l = 0;
        int r = k-1;
        
        int people = 200000001;
        while(r <= stones.length-1){
            int maxStone = -1;
            for(int i = l;i<=r;i++){
                maxStone = Math.max(maxStone, stones[i]);
            }
            people = Math.min(people, maxStone);
            r++;
            l++;
        }
        int answer = people;
        return answer;
    }
}

 

정확도는 맞았지만, 시간 초과가 나왔다.

 

따라서 이분탐색을 적용했다.

사람수를 기준으로 건널 수 있는지 없는지 계속 확인하는 것이다.

class Solution {
    public int solution(int[] stones, int k) {
        int answer=0;
        
        int minPeople = 0;
        int maxPeople = 200000001;
        
        while(minPeople <= maxPeople){
            int mid = (minPeople + maxPeople)/2;
            if(binarySearch(stones, k, mid)){
                minPeople = mid + 1;
                answer = mid;
            }
            else{
                maxPeople = mid-1;
            }
        }
        return answer;
    }
    static boolean binarySearch(int[] stones, int k, int m){
        int cnt = 0;
        for(int i=0;i<stones.length;i++){
            if(stones[i] < m){
                cnt++;
                if(cnt >= k)return false;
            }
            else cnt=0;
        }
        return true;
    }
}