Programmers - 징검다리 건너기

문제 링크

처음 떠올린 풀이 방법은 시뮬레이션이었다.

1. stones에 0을 제외한 최소 값만큼 건넌다.
2. 건널 수 있는지 확인 후 건널 수 있으면 1을 반복

하지만 다리의 개수가 20만개이고 다리에 써진 숫자가 2억이라 이 방법으로는 풀 수 없었다.

다른 풀이방법이 떠오르지 않아서 질문하기를 확인하니까 이분탐색으로 풀면 된다고 써있었다.
이분탐색으로 풀 수 있다는 법을 확인하니까 바로 풀이가 떠올랐다.

possible() : n-1명의 사람이 건넌 이후의 상태에서 마지막 1명이 건널 수 있는지 여부를 확인.

처음에는 python으로 구현했는데 시간초과가 발생했다.
아무리 봐도 로직 문제는 아닌 것 같아 같은 로직을 java로 구현하였더니 통과가 되었다.
추측으로는 Array copy를

temp = stones[:]

로 했는데 최대 20만개를 copy하는게 시간이 많이 걸려서 인것 같다.

import java.util.*;

class Solution {

    int[] original;

    public int solution(int[] stones, int k) {
        original = stones;

        int l = 1;
        int r = Arrays.stream(stones).max().getAsInt();
        int answer = 0;

        while(l<=r){
            int mid = (l+r)/2;
            if(possible(mid,k)){
                answer = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }

        return answer;
    }

    private boolean possible(int n,int k){
        int zeroCount = 0;
        int[] copied = new int[original.length];
        System.arraycopy(original,0,copied,0,original.length);

        for(int i=0;i<copied.length;i++){
            copied[i] -= n-1;
            zeroCount = copied[i] > 0 ? 0 : zeroCount+1;
            if(zeroCount==k)
                return false;
        }
        return true;
    }
}