[Programmers] 징검다리 건너기

정확성과 효율성을 같이 보는 문제이다.

이 문제를 요구조건 그대로 구현한다면 어렵지 않게 풀수있고, 정확성부분에선 전부다 맞칠 수 있다. 하지만 효율성 부분에 있어선 시간초과가 나기 쉽다. 이 문제 같은 경우는 효율성을 위해선 알고리즘 기법을 사용해야하는데 나는 파라메트릭 서치 를 사용하였다. 파라메트릭 서치란 다음과 같다.

파라메트릭 서치 : 최적화 문제를 결정 문제로 바꾸어 푸는 것. left, right, mid 값을 사용하여 특정값을 찾는 이분탐색과 상당히 유사하며 logN의 시간복잡도를 가짐. 이분 탐색과의 차이점은 결정문제인지 아닌지의 차이.

문제로 다시 돌아가서 제한사항을 본다면 지나가는 친구들의 수는 무한이라고 주어졌다. 하지만 생각해보면 배열의 최소수인 200,000,000까지 친구들이 지나갈수 있다고 생각할수 있다. 즉 K값을 신경안쓴다는 조건하에 최소1, 최대 200,000,000의 친구들이 지나갈수 있다고 생각하고, 이걸 파라메트릭 서치의 개념으로 생각한다면 mid값을 이용하여 N명일때 지나갈수 있냐 없냐 로 생각할수 있다.
즉, 입출력 예시로 본다면 stones배열에서 가장큰 값인 5가 최대가 되고, 최소는 1이된다. 다시 말하자면 left=1, right=5인 파라메트릭 서치가 되고 결정은 mid명일때 지나갈수 있냐 가 될수 있다.

어려운 알고리즘은 아니지만 익숙치 않아서 도움을 받아 풀었다. 상당히 유용한 알고리즘이고 다양한 형태로 많이 나오기때문에 반복학습이 필요할 것 같다.

package programmers;
 
 
public class Sloution_2019카카오겨울_징검다리건너기 {
    public static void main(String[] args) {
        int[] stones= {2,4,5,3,2,1,4,2,5,1};
        int k=3;
        System.out.println(solution(stones,k));
    }
    
    static int solution(int[] stones,int k) {
        int max=0;
        for(int i=0;i<stones.length;i++)
            max=Math.max(max, stones[i]);
        
        int left=1;
        int right=max;
        
        int result=0;
        while(left<=right) {
            int mid=(left+right)/2;
            
            boolean possible=check(stones,mid,k);
 
            if(possible==true) {
                result=Math.max(result, mid);
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        return result;
    }
    
    static boolean check(int[] stones, int mid,int k) {
        
        int len=0;
        
        for(int i=0;i<stones.length;i++) {
            if(stones[i]-mid+1 <=0) {
                len+=1;
                
                if(len==k)
                    return false;
            }else
                len=0;
        }
        
        return true;
    }
}