문제 - 징검다리 건너기

문제 설명

1. 징검다리를 건널 때 디딤돌을 밟고 지나간다.
2. 디딤돌을 밟을 때에는 디딤돌의 숫자가 줄어든다.
3. 디딤돌의 숫자가 0이 되면 해당 디딤돌을 밟지 못한다.
4. k만큼의 디딤돌을 건너 뛰고 걸을 수 있다.
5. 무조건 가장 가까운 디딤돌로만 건너뛸 수 있다.
6. 최대 몇명까지 징검다리를 건널 수 있는지 출력

문제 접근

한명 씩 디딤돌을 건너면서 건널 수 있는지 못하는 지 완전탐색느낌으로 찾으면 효율성테스트에서 안좋은 결과를 받을 거 같아서 다른 방법을 생각해보았다.

1. 슬라이딩 윈도우

• 이 방법은 어떻게 하는지 이해가 되지 않는다..

2. 이분탐색

• 최소 건널 수 있는 인원과 최대 건널 수 있는 인원의 중간값으로 건널 수 있는 지 확인한다.
• 건널 수 있다면 중간값을 좀더 커지게 하기 위해 최소 건널 수 있는 인원을 늘려준다.
• 건널 수 없다면 중간값을 좀더 작게 해야되므로 최대 건널 수 있는 인원을 줄여준다.
• 건널 수 있는지 판단조건
  1. 건너뛰는 디딤돌의 갯수가 최대 갯수 k이거나 큰 경우에는 건너지 못하므로 false 출력
  2. k보다 작을 경우에는 건널 수 있어서 true 출력

코드

이분탐색

import java.util.*;
class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        //최소한으로 건널 수 있는 사람 수
        int left = 1;
        //최대로 건널 수 있는 사람 수
        int right = -1;
        
        for(int stone : stones)
        {
            right = Math.max(stone,right);
        }
        
        while(left <= right)
        {
            //현재 건널 수 있는 사람의 수
            int mid = (left+right)/2;
            
            if(isCrossStones(mid,k,stones))
            {
                //해당 인원으로 건너기 가능
                left = mid + 1;
                answer = mid;
            }else{
                //해당 인원으로 건너기 불가능
                right = mid - 1;
            }
        }
        
        return answer;
    }
    
    private boolean isCrossStones(int friend, int k, int []stones){
        //뛰어넘는 디딤돌들
        int skip = 0;
        
        for(int i = 0;i<stones.length;i++)
        {
            if(stones[i] - friend < 0)
            {
                skip++;
            }
            else
                skip = 0;
            
            if(skip >= k)
            {
                return false;
            }
        }
        
        return true;
    }
}