[프로그래머스] 이분탐색 - 징검다리 (Swift 풀이)

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

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

난이도 최상.... 접근 방법이 떠오르지 않아 며칠간 고민했던 문제이다.

다루어야 하는 범위가 큰 만큼, 이분탐색으로 접근해야 타임리밋에 걸리지 않는다!

 

이분탐색의 기준은 N개의 바위를 제거했을 때, 특정 X 거리가 최소값이 될 수 있는지를 판단하기 위한 것으로 두면 된다.

다시 말하자면, X가 가능한 범위는 1부터 distance까지 가능하므로, 1~distance의 중간값을 X로 두고 먼저 판단해보는 것이다.

// 범위
var start = 1
var end = distance

// 중간 값을 X로 둔다: 최소가 될 수 있는가??
let mid = (start+end)/2

 

그렇다면 X가 최소가 될 수 있을지 어떻게 판단할까??

 

먼저, 모든 바위 사이의 거리를 구하면서 지울지 아닐지 판단한다.

바위 사이의 거리를 구하는 방법은, 처음에는 기준 바위를 0으로 두고 모든 바위를 탐색한다.

탐색하면서 현재 바위와 기준 바위의 차를 구해서 거리를 계산한다.

 

바위 사이의 거리가 X보다 작다면 일단 지우고 보는 것이다. (제거 카운트 증가)

바위 사이의 거리가 X 이상이라면 지우지 말고, 기준바위를 현재 바위로 업데이트 한다.

var indicator = 0
var deleteCnt = 0

for rock in rocks {

    // 현재바위 - 기준바위
    if rock-indicator < mid {
        // 제거 카운트 증가
        removeCnt += 1
    } else {
        // 기준 바위를 현재 바위로 업데이트
        indicator = rock
    }
}

그리고, 마지막 바위와 도착점 사이의 거리까지 계산해주어야 한다!

// 마지막 바위와 도착점 사이 거리 계산
if distance - indicator < mid {
    removeCnt += 1
}

 

그렇게 바위를 지우다가 N개 보다 많이 지우게 되면 X는 최소가 될 수 없다고 판단한다.

=> 더 작은 값을 찾기 위해 앞 부분 탐색

 

모든 바위 사이의 거리를 다 탐색했는데도, N개 이하로 지웠다면 X는 최소가 될 수 있다고 판단한다.

=> 일단 값을 저장하고, 더 큰 값이 있을지도 모르니까 뒷부분 탐색

if removeCnt <= n {
    // mid보다 거리가 짧아서 지운 개수가 n보다 작으면 뒷 부분 탐색
    answer = mid
    start = mid + 1
} else {
    // mid보다 거리가 짧아서 지운 개수가 n보다 크면 앞 부분 탐색
    end = mid - 1
}

 

이 모든 과정은 반복문으로 처리된다.

반복문의 조건은 start <= end다.

 

최종적으로 완성된 코드 (Swift)

import Foundation

func solution(_ distance:Int, _ rocks:[Int], _ n:Int) -> Int {
    let rocks = rocks.sorted()
    var answer = 1
    var start = 1
    var end = distance
    
    while(start <= end) {
        let mid = (start+end)/2
        var indicator = 0
        var removeCnt = 0
        
        // mid보다 거리가 짧으면 바위 제거
        for rock in rocks {
            if rock-indicator < mid {
                removeCnt += 1
                if removeCnt > n { break }
            } else {
                indicator = rock
            }
        }
        
        // 마지막 바위와 도착점 사이 거리 계산
        if distance - indicator < mid {
            removeCnt += 1
        }
        
        // 제거한 바위가 n이하라면 mid가 최소값이 될 수 있다.
        if removeCnt <= n {
            answer = mid
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    
    return answer
}