[코틀린] 프로그래머스 lv3 : 징검다리 건너기 (카카오 기출문제 풀이)

문제 풀러 가기!

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.
징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.
디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

[제한사항]
징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
stones 배열의 크기는 1 이상 200,000 이하입니다.
stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
k는 1 이상 stones의 길이 이하인 자연수입니다.

풀이

이 문제의 최대 N값은 2억이기 때문에 완전 탐색을 한다면 엄마 나 군대 갔다올테니 컴퓨터 끄지마를 시전하실 수도 있습니다.

따라서 저희는 이분 탐색을 시도해볼 수 있습니다.

풀이를 보시기 전에 이분 탐색에 대한 충분한 이해가 필요합니다.
이분탐색, upper bound, lower bound에 대해 숙지하시면 이해하는데 많은 도움이 되실거에요.

1. 로직 설명

이 문제의 풀이 로직은 다음과 같습니다.

min = 0, max = 200_000_000

반복문 시작: min < max
	mid = (min + max) / 2
    만약, mid명의 인원으로 모든 징검다리를 건널 수 있다면,
    	min = mid + 1 (더 많은 인원을 투입해본다.)
    만약 건널 수 없다면,
    	max = mid (더 적은 인원을 투입해본다.)
반복문 종료

정답 반환: min - 1

정답으로 min - 1을 한 이유는 upper bound 를 이용하였기 때문입니다.

upper bound 의 특성은 이분 탐색을 통하여 목표값 바로 다음으로 큰 수를 찾아내는 알고리즘입니다. 따라서, 위 로직은 정답 값보다 1 만큼 더 많은 값을 리턴하기 때문에, -1 처리를 해주는겁니다.

2. 징검다리를 건널 수 있는지 판별하는 함수 정의

앞서 말씀드린 로직을 구현하기 위해서는 특정 인원(mid)이 징검다리를 건널 수 있는지 확인해야합니다. 이 로직도 효율성에 신경을 써주어야합니다. 만약 한 명씩 징검다리를 건너도록 프로그래밍을 하면 최대 2억번의 연산을 하기 때문입니다.

문제에서 최대 k거리 만큼 점프를 할 수 있다고 정의되어 있기 때문에, 전체 인원이 밟을 수 없는 연속되는 돌을 카운트 해주어야합니다.

private fun crossBridge(k: Int, mid: Int, bridge: IntArray): Boolean {
    // mid 만큼의 인원이 건널 수 있는지 확인한다.
    // 한 번에 뛸 수 있는 징검다리가 k를 초과한다면 건널 수 없다.
    var cntZero = 0 // 밟을 수 없는 연속되는 돌의 개수
    for (item in bridge) {
        if (item - mid < 0) {
            cntZero++ // 모든 사람이 돌을 밟을 수 없음
        } else {
            cntZero = 0 // 모든 사람이 이 돌을 밟을 수 있음
        }
        // 밟을 수 없는 디딤돌이 연속해서 k개가 된다면, 건널 수 없다.
        if (cntZero == k) {
            return false
        }
    }
    return true
}

Source Code

package Kakao_Internship_2019.징검다리_건너기

class Solution {
    fun solution(stones: IntArray, k: Int): Int {
        var min = 0
        var max = 200_000_000
        // 구하고자 하는 값은 `친구들의 최대` 이기 때문에 upper bound 를 고려해볼 수 있다.
        while (min < max) {
            val mid = (min + max) / 2

            if (crossBridge(k, mid, stones)) {
                // 만약 건널 수 있으면 mid값을 더 높여봐야한다.
                min = mid + 1
            } else {
                max = mid
            }

        }
        return min - 1
    }

    private fun crossBridge(k: Int, mid: Int, bridge: IntArray): Boolean {
        // mid 만큼의 인원이 건널 수 있는지 확인한다.
        // 한 번에 뛸 수 있는 징검다리가 k를 초과한다면 건널 수 없다.
        var cntZero = 0 // 밟을 수 없는 연속되는 돌의 개수
        for (item in bridge) {
            if (item - mid < 0) {
                cntZero++ // 모든 사람이 돌을 밟을 수 없음
            } else {
                cntZero = 0 // 모든 사람이 이 돌을 밟을 수 있음
            }
            // 밟을 수 없는 디딤돌이 연속해서 k개가 된다면, 건널 수 없다.
            if (cntZero == k) {
                return false
            }
        }
        return true
    }
}