[Swift Algorithm] 64062 징검다리 (2019카카오 겨울인턴십)

programmers.co.kr/learn/courses/30/lessons/64062

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

 

풀이방법

범위가 2억이기때문에... 그냥풀면 분명이 시간초과가 걸릴거라고 생각...햇고..

1명씩 건너도록 단순하게 푼경우.. 역시나 시간초과에 걸린...

private func solutionP64062(_ stones:[Int], _ k:Int) -> Int {
    var stones = stones
    var isJump = true
    var result = 0
    
    while true {
        var zeroCount = 0
        for stone in stones {
            if stone <= 0 {
                zeroCount += 1
            } else {
                zeroCount = 0
            }
            
            if zeroCount >= k {
                isJump = false
                break
            }
        }
        
        if !isJump {
            break
        }
        
        for i in stones.indices {
            stones[i] -= 1
        }
        result += 1
    }
    print(result)
    return result
}

 

반대로

1명씩 건너는게아닌

2명

3명

4명

10명

100명

...

n명씩 건너는 경우를 보면돼요

 

억단위니까 효율적인 알고리즘을 분명써야겟죠?

이진탐색을 사용할거에요

 

최소1명 ~ 최대2억명이니까

중간값인 1억부터 비교를 하는거죠

 

[1~1억] / [1억~2억]

1억명이 건넛을때 모두 건널수있다면 오른쪽범위를

1억명이 건넛을때 건널 수없었다면 왼쪽범위를 다시 탐색해가면서

최적의 해를 찾아가는 과정이에요

 

private func solutionP64062(_ stones:[Int], _ k:Int) -> Int {
    var left = 1
    var right = 200_000_000
    
    func isLeftAare(stones: [Int], mid: Int) -> Bool {
        var zeroCount = 0
        for stone in stones {
            if stone - mid <= 0 {
                zeroCount += 1
            } else {
                zeroCount = 0
            }
            
            if zeroCount >= k {
                return true
            }
        }
        return false
    }
    
    while left < right  {
        let mid = (left + right) / 2
        if isLeftAare(stones: stones, mid: mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}