[프로그래머스] 징검다리 건너기 - JAVA

문제링크 🚩

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

프로그래머스

 

​

📕 문제 접근 📕

해당 문제를 해결하기 위해서는 다음과 같은 조건을 만족해야 한다. 

 

1. 디딤돌의 숫자를 한 번 밟을 때 마다 1씩 줄어든다. 

2. 0이 되면 해당 돌을 밟을 수 없다. 

3. 무조건 가장 가까운 돌로만 건널 수 있다. 

4. 최대로 건너뛸 수 있는 돌은 K개 이다. 

 

"핵심 아이디어"

돌의 숫자 - 뛸 수 있는 인원이 <0 일 때 돌을 건너뛴다. 

건너뛴 돌의 수가 K수와 같아진다면 건널 수 없다. 

 

for(int stone : stones){
            if(stone - friends < 0){
                jump++;
            }else{
                jump = 0;
            }
            if(jump == k){
                return false;
            }
        }

 

뛸 수 인원이 20,000,000명 일 수 있기 때문에 1명부터 20,000,000을 모두 계산하는 것은 매우 비효율적이다. 

이분탐색 기법을 활용하여 최대의 인원에서 / 2씩 수행하며 최소 값을 구하는 것이 현명하다.

 

 

💻 Code 💻

 

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        int min =  1;
        int max = 200000000;
        
        while(min <= max){
            int mid = (min + max) / 2 ;
            // 넘어갈 수 있다면 
            if(isPossible(stones, k, mid)){
                min = mid +1 ;
                answer = Math.max(answer, mid);
            }else{
                // 못 넘어간다면 
                max = mid - 1;
            }
            
        }
        return answer;
    }
    
    public static boolean isPossible(int[] stones, int k, int friends){
        int jump = 0;
        for(int stone : stones){
            if(stone - friends < 0){
                jump++;
            }else{
                jump = 0;
            }
            if(jump == k){
                return false;
            }
        }
        return true;
    }
}