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

문제 풀이 아이디어

완전탐색?

문제만 딱 보면 바위 중에 n개를 뽑아서 제거하고 간격을 구하는 조합 문제로 풀면 딱 좋을 것 같습니다. 하지만 바위가 50,000개나 있습니다. 이거를 조합으로 풀면…. 100% 시간 초과입니다.

이분탐색

이 문제는 이분 탐색으로 풀어야 합니다. 파라메트릭 서치로 풀어야 하죠. 파라메트릭 서치는 특정 범위 내에서 중간 값을 구하고 조건에 만족하는지 체크하면서 최적화된 값을 구해나가는 방법입니다. 쉽게 말하면 최적화된 하나의 값을 구하기는 문제를 연속된 O/X 문제로 바꾸어서 푸는 방법입니다.

조건 = 제거하는 바위의 갯수

파라메트릭 서치를 위해서는 하나의 고정된 기준이 있어야 합니다. 이 기준을 근거로 중간 값이 조건에 만족하는지 아닌지 구할 수 있습니다. 우리에게 주어진 단 하나의 기준이 있습니다. 바로 제거하는 바위의 갯수입니다. 제거하는 바위의 갯수 기준으로 O/X 문제를 설계하면 됩니다.

구해야 하는 값 = 바위 사이의 간격의 최솟값

우리가 구해야 하는 값은 바위 사이의 간격의 최솟값입니다. 이 값을 1 ~ distance의 사이에서 최적화된 값을 구하면 됩니다.

일반적인 파라메트릭 서치와 다른 점

모든 제거가 끝난 후 바위 사이의 최대 간격을 mid로 하고 부숴야하는 바위 갯수를 구합니다. 바위 갯수가 n보다 작거나 같다면 정답을 업데이트합니다.

여기서 일반적인 파라메트릭 서치라면 mid를 그대로 정답에 업데이트 하는 경우가 많습니다. 하지만 우리가 설정한 mid는 바위 사이의 최대 간격입니다. 하지만 우리가 찾는 값은 간격 중에 “최솟값"입니다. 따라서 최솟값은 별도의 변수를 지정해서 따로 저장해두어야 합니다.

코드

func solution(_ distance:Int, _ rocks:[Int], _ n:Int) -> Int {
    
    // 이분 탐색 시작점, 끝점
    var start = 1
    var end = distance
    
    // 답 저장용 변수
    var ans = 0
    
    // 바위 정렬 + 앞뒤에 출발지점 및 도착지점 추가
    let rocks = [0] + rocks.sorted() + [distance]
    
    // 이분탐색 구현
    while start <= end {
        let mid = (start + end) / 2
        
        // 제거한 바위 갯수
        var removed = 0
        
        // 현재 바위 위치 (= 파괴 안한 마지막 바위)
        var now = 0 //👉 초기 값은 출발지점
        
        // 바위 사이의 최소 간격을 저장하는 변수
        var minGap = Int.max
        
        // 바위들을 순회하면서 (출발지점 제외)
        for i in 1..<rocks.count {
            // 현재 바위 ~ 다음 바위까지의 거리 (now ~ i 사이의 다른 바위들은 제거됨)
            let gap = rocks[i] - rocks[now]
            
            // 거리가 mid 보다 작으면
            if gap < mid {
                removed += 1 //👉 i 번째 바위 제거
            // 거리가 mid 보다 크다면
            } else {
                // 최소 간격 업데이트하고
                minGap = min(minGap, gap)
                now = i //👉 현재 바위 위치 이동 (= 파괴 안한 마지막 바위)
            }
        }
        
        // n개 보다 더 많이 부쉈다면 간격 줄이기
        if removed > n {
            end = mid - 1
        // n개 보다 같거나 적게 부쉈다면
        } else {
            start = mid + 1 //👉 간격 늘리기
            ans = minGap //👉 답 갱신하기
        }
    }
    
    return ans
}