프로그래머스 징검다리 Kotlin (이분탐색)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43236

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

문제 설명

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

입출력 예

입출력 예 설명

문제에 나온 예와 같습니다.

출처

※ 공지 - 2020년 2월 17일 테스트케이스가 추가되었습니다.

풀이

이분 탐색 문제이다.

전체적인 풀이는 다음과 같다.

1. rocks를 정렬하고 0(출발지점), distance(도착지점)을 추가하여 바위 사이의 거리 배열을 만든다.

2.이분 탐색을 이용해 답을 찾는다.

 

우리는 어떠한 답을 찾아야 하는가.

바위를 n개 골라서 제거했을 때 나오는 거리의 최솟값 중 가장 큰 최솟값을 찾아야 된다.

그러면 n개의 바위를 조합으로 뽑아서 제거한 후, 각 바위 사위의 거리들을 계산하고, 각 조합마다 최솟값을 뽑고, 이중 최댓값을 찾으면 된다. 하지만 입력의 크기를 보면 바위는 50000개, distance는 10억이다. nC50000은 절대 돌릴 수 없으니 다른 방법이 필요하다.

요구 사항을 자세히 들여다 보면, 방법이 나온다.

우리가 찾는 답이 X라할 때, 이 X는 n개의 바위를 제거했을 때 각 바위 사위의 거리 중 최솟값으로, X보다 작은 값이 없어야 한다.

그러면 주어진 바위들의 리스트에서 X를 답으로 만들려면 X보다 작은 값을 모두 제거해야 한다.

이때 우리는 바위를 제거하는 데에 n이라는 갯수 제한이 있으므로, X를 답으로 만들기 위해 n+1개 이상 바위를 제거했다면 이는 정답이 될 수 없다!!

그럼 이분 탐색을 어떤 값을 기준으로 해야 할지 보인다.

우리가 찾는 X라는 값을 이분 탐색을 통해 찾는 것이다.

X의 범위는 1 ~ distance다.

X는 n개 바위를 제거했을 때 나오는 거리의 최솟값 중 가장 큰 최솟값이기 때문에

rocks가 {1}이고 distance가 2인 경우

0 1 2로 X는 1이 될 수 있고,

0 1 10억이면 X는 10억-1이 될 수 있다.

 

그럼 이분 탐색의 mid가 곧 X값이고, 이제 어떠한 기준에 따라 이분 탐색의 오른쪽을 탐색할 것인지, 왼쪽을 탐색할 것인지 정의를 내려주면 된다.

예제를 예로 들면 바위들은 start와 distance를 추가해 다음과 같은 형태이다.

0 2 11 14 17 21 25 (입력받은 바위들을 정렬하고 앞 뒤에 start, distance를 추가했다.)

이 값들은 바위의 x좌표를 의미하므로 바위 간의 거리 차이 배열로 바꾸어 주자.

2 9 3 3 4 4

이제 mid값을 X라고 보고, X보다 작은 값들을 위의 배열에서 없애보자.

(그냥 앞에서부터 지우면 된다.)

mid가 5라고 하면 제일 처음 나오는 2가 지워지고 뒤의 거리와 합산되어 11이 된다.

11 3 3 4 4

이후 3이 지워지고 뒤의 거리와 합산되어 6이 된다.

11 6 4 4

이후 4가 지워지고 뒤의 거리와 합산되어 8이 된다.

11 6 8

더 이상 지울 수 있는 게 없다.

n개 만큼만 지울 수 있는데 mid가 5일 때는 3개를 지워야 한다.

따라서 mid를 낮추어 이분 탐색을 이어간다.

만약 mid보다 작은 값이 n개 보다 같거나 적다면 mid를 높여 이분 탐색을 이어가면 된다.(X는 가능한 답 중 최댓값이어야 하므로.)

코드

class Solution {

    lateinit var diffArr: IntArray

    //sort
    //binarySearch (ParametricSearch)
    fun solution(distance: Int, rocks: IntArray, n: Int): Int {
        //preset
        var s = 1
        var e = distance
        var answer = 0
        rocks.sort()
        diffArr = IntArray(rocks.size+1)
        diffArr[0] = rocks[0]
        diffArr[rocks.size] = distance-rocks[rocks.size-1]
        for(i in 0 until rocks.size-1){
            diffArr[i+1] = rocks[i+1]-rocks[i]
        }
        //solve
        while(s<=e){
            val mid = (s+e)/2
            var cur=0
            var removed=0

            //mid보다 작은 것들 삭제
            for(i in diffArr.indices){
                cur += diffArr[i]
                if(cur < mid) removed++
                else cur = 0
            }
            if(n<removed){
                e = mid-1
            }
            else{
                answer = mid
                s = mid+1
            }

        }
        return answer
    }
}