[프로그래머스, Java] Level3: 징검다리 건너기

 

문제분석

 

문제를  이해해보자.

 

니니즈 친구들 :무한

징검다리 갯수 : 최대 20만

징검다리 카운트: 최대 2억

니니즈들의 점프력:  0<K<징검다리갯수 

 

 

니니즈들은 무조건 자기 앞에있는 징검다리를 먼저밟는다.

징검다리를 건너다가,  징검다리 카운트가 0이된다면   니니즈들은 0이아닌 징검다리로 "점프"한다.

 

0이아닌 징검다리로 "점프"하지 못하면 그때 최대 니니즈수를 반환하면된다.

 

즉,  최대 니니즈 친구들을 N이라고 할때, 

모든  징검다리 카운트를 N만큼뺀뒤    니니즈들의 점프력만큼 0인징검다리가 연속으로 있어야한다.

 

 

 

필자의 처음 접근은 이렇다.

 

1.  징검다리가 0인 연속 구간을 찾자!

 

for(징검다리 전체구간)

  for(니니즈들 점프력)

 

이렇게 2차 배열을 만들어서  니니즈들이 최대로 건널수있는 징검다리구간 갱신하는 식으로 접근했다.

 

 

But, 정확성 100%  효율성 에러

 

 

 

-----------------------------------------------------------------------------------------------

 

2. 니니즈들의 숫자로 이분탐색

 

이 문제에서 니니즈들은 최대 2억명이 가능하다.

 

2억으로  이분탐색을 진행하면  log2(2억) = 26~27 의 연산만으로 값을 찾을수있다고 한다.

 

즉,  26*O(N) 이 가능하다.

 

니니즈들의 숫자로 이분탐색을 하는데, 조건을 이렇게 넣는다.

 

니니즈들이 이 다리를 전원 건널수 있는가? 다.

 

만약 니니즈들이 전원 건너지못하면,  니니즈들의 인원을 줄여야하니  DOWN

 

니니즈들이 전원 건너면,  더욱 니니즈들이 건널 가능성이 있으니, UP을한다. 

 

니니즈들이 다리를 건널수있는 여부를 메소드로 뽑아 따로 계산을 해두자.

문제풀이

import java.util.*;
class Solution {
    public int solution(int[] stones, int k) {
        int answer =0;
        
        //연속된 K중 가장 수가 답
        
        int max =200000000;
        int min=1;
    
        while(min<=max){
            
            int mid=(max+min)/2;
            
            if(calculate(mid,k,stones)){
                 min=mid+1;
                answer=mid;
            }
            else{
                max=mid-1;
            }
             
        }
        
       return answer;
    }
    
    public boolean calculate(int mid, int k,int[] stones){
        
        int count=0;
        
        for(int stone:stones){
            
            if(stone<mid){
                count++;
            }
            else{
                count=0;
            }
            
            if(count==k){
                return false;
            }
        }
        return true;
    }
}