코딩테스트 연습 - 징검다리 건너기

문제 풀이 아이디어

stone 배열의 크기를 M이라고 하고 stone 배열 원소의 크기를 N이라고 하고 시간복잡도를 설명하겠습니다.

예시에 나온대로 순차적으로 탐색하면?

처음에는 예시에 나온대로 1명씩 다리를 건너면서 cnt 변수에 += 1 해가면서 더 이상 건널 수 없을 때까지 다리를 건너고 최종적으로 cnt를 리턴하는 방식으로 코드를 짜봤습니다.

다리를 건널 수 있는지 확인하기 위해서는 순차탐색을 통해서 중간에 없어진 디딤돌의 갯수를 세야 합니다. 따라서 다리를 건널 수 있는지 확인하는 함수의 시간복잡도는 O(M)입니다. M은 최대 200,000이므로 큰 문제가 되지는 앉습니다.

하지만 문제는 N입니다. N이 최대 2억이므로 순차적으로 cnt를 더해가는 방법을 구현하면 시간복잡도는 O(M * N)이 될 텐데 N의 크기가 너무 크기 때문에 100% 시간 초과입니다.

N의 크기를 고려하면 더 효율적인 알고리즘이 필요합니다.

이분 탐색은 O(logN)

아래 코드에서 다리를 건널 수 있는지 확인하는 함수는 n명의 인원이 다리를 건널 수 있는지 true or false로 반환합니다. 특정한 값을 찾기 위해서 연속된 O / X 퀴즈를 활용하는 방법인 parametric search를 활용하기에 적절한 함수입니다. 이분 탐색을 하면서 특정 n명이 다리를 건널 수 없는지 확인하면서 최적의 n을 구하면 됩니다.

이분탐색을 활용하면 최종적으로 시간복잡도는 O(MlogN)으로 연산 시간을 훨씬 줄일 수 있습니다.

Tip!!!

다른 분들의 설명을 참고해보니 많은 분들이 N이 2억을 보는 순간 이분탐색을 떠올리신 분들이 많았다고 하더라구요. 터무니 없이 큰 값이라 O(logN)의 알고리즘이 아니면 풀 수 없기 때문입니다. 이렇게 문제 속에도 힌트가 숨어 있을 수도 있습니다!

코드

func solution(_ stones:[Int], _ k:Int) -> Int {
    
    // n명의 인원이 다리를 건널 수 있는지 확인하는 함수 -> O(M)
    func isAvailable(_ n: Int) -> Bool {
        // (n - 1)명이 건너고 난 이후에 n번째 사람이 건널 수 있는지
        var gap = 0
        
        // 뛰어넘어야 하는 디딤돌이 연속으로 k개 이상이면 건널 수 없음.
        for i in 0..<stones.count {
            if stones[i] - (n - 1) <= 0 {
                gap += 1
                if gap > k - 1 { return false }
            } else {
                gap = 0
            }
        }
        
        return true
    }
    
    // 이분 탐색을 활용한 Parametric Search
    var start = 0
    var end = 200000000
    var ans = 0
    
    while start <= end {
        let mid = (start + end) / 2
        
        if isAvailable(mid) {
            start = mid + 1
            ans = mid
        } else {
            end = mid - 1
        }
        
    }
    
    return ans
}