프로그래머스 징검다리 건너기

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

• 징검다리의 디딤돌들에 숫자가 있고, 한 명이 밟을 때마다 1씩 감소한다.
• 한 디딤돌의 카운트가 0이 되면 더 이상 밟을 수 없으며 건너 뛰어야 한다.
• 최대 k거리까지 건너뛸 수 있으며 다리를 건널 수 있는 최대 인원을 구한다.

아래는 예시이다.

징검다리 - [2, 4, 5, 3, 2, 1, 4, 2, 5, 1], k = 3

stones의 배열 크기가 최대 200,000이고 각 원소들의 값이 최대 200,000,000이다.

또한 효율성 테스트가 있기 때문에 시뮬레이션 방법으로는 한계가 있다고 보았다.

따라서 생각난 것이 이분탐색 방법인데, 인원 x명이 다리를 모두 건널 수 있는가? 를 기준으로 잡는 것이 좋아 보였다.

이분탐색에서 mid 값에 해당하는 x명이 다리를 모두 건널 수 있다면, mid를 start + 1로 옮겨 다시 건널수 있는지를 반복해서 확인하면 될 것 같았다.

내가 생각한 x명이 모두 다리를 건널 수 있는지 확인하는 방법은 간단하다.

x - 1명이 지나갔다고 치고, 주어진 stones의 모든 값들을 x-1만큼 감소시킨다. (음수가 될 경우 0으로 고정한다)

그리고 x번째 친구가 건너가는데, 0이 k개 연속으로 등장하는지 여부를 확인한다.

0이 k개 연속으로 등장하면 건널 수 없고, k-1개까지 연속으로 등장하면 건널 수 있다고 판단할 수 있다. (해당 인원이)

징검다리 - [2, 4, 5, 3, 2, 1, 4, 2, 5, 1], k = 3

이 케이스를 예로 들고, 3명이 건널 수 있는지 확인해본다.

2명이 건너면 징검다리는 [0, 2, 3, 1, 0, 0, 2, 0, 3, 0]이 될 것이다.

k=3이므로 0이 연속 2개까지 등장해도, 마지막 친구는 건너뛰어 다리를 건널 수 있다.

따라서 3명은 해당 다리를 건널 수 있다.

그럼 4명이 건널 수 있는지 확인해 본다.

3명이 건너면 징검다리는 [0, 1, 2, 0, 0, 0, 1, 0, 2, 0]이 될 것이다.

마지막 친구가 건너려고 할 때 최대 3칸을 뛸 수 있으나, 중간에 0이 3연속 등장하는 구간에서 막히게 되어 건널 수 없다.

이 이분탐색 방법으로 코드를 구현한다.

class Solution {
    fun solution(stones: IntArray, k: Int): Int {
        var start = 0
        var end = stones.maxOrNull() ?: 0

        var max = 0
        while(start <= end){
            val mid = (start + end) / 2

            if(canArrive(stones, k, mid)){
                start = mid + 1
                max = mid
            }else{
                end = mid - 1
            }
        }
        return max
    }

    fun canArrive(stones: IntArray, k: Int, num: Int): Boolean{
        val copy = stones.clone()
        for(i in copy.indices){
            copy[i] = if(copy[i] - num + 1 < 0) 0 else copy[i] - num + 1
        }

        var maxZero = 0
        var zeroCnt = 0
        for(i in copy.indices){
            if(copy[i] == 0) {
                zeroCnt++
                if(maxZero < zeroCnt) maxZero = zeroCnt
            } else zeroCnt = 0
        }

        return k > maxZero
    }
}