[프로그래머스] (이분탐색) 징검다리(C++)

징검다리 (Level 4)

문제

전체 문제 보기

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

접근법

이 문제에서 요구하는 것은 전체 징검다리 바위들 중에서 n개의 바위를 제거했을 때 "바위들 간격의 최솟값이 가장 큰 값"이다. 어떤 바위를 제거하냐에 따라서 간격의 최솟값이 변할 수 있는데 이중 최솟값이 가장 큰 값을 구하는 것이다. 이 문제는 이분 탐색으로 접근하면 쉽게 해결할 수 있다. 이분 탐색을 활용할 경우, 바위를 제거하는 효율적인 방법이 무엇인지는 신경 쓰지 않아도 된다.

 

이분 탐색을 하기위해서 먼저 무엇을 탐색할 것이지 정하자. 우리는 임임의 최솟값 mid가 n개의 바위를 제거했을 때 가능한 값인지 유효성 검사를 해야 한다. 유효성 검사라는 것은 다음과 같다. 예시에서 주어진 상황을 생각해보자. (바위의 위치는 처음에 정렬을 한 후 사용해야 한다. 여기에서는 정렬이 되어있음을 가정하고 설명한다.)

[0] [2, 11, 14, 17, 21] [25] / n = 2

위와 같이 바위의 위치가 주어졌고 바위를 2개만 삭제한다고 했을 때 최솟값이 10인 경우가 가능할 까? 어떤 방식으로든 바위를 2개만 지웠을 때 모든 바위의 간격이 최소 10 이상이 나오도록 만드는 것을 불가능하다. 그렇다면 우리는 10보다 더 작은 경우의 수, 예를 들면 5는 가능한지 확인해야 할 것이다.

 

이런 유효성 검사를 조금더 명확히 나타내면 다음과 같을 것이다. 먼저 최소 간격이 10이라는 말은 바위를 n번(여기서는 2번) 삭제해서 모든 바위의 간격을 10 이상으로 만들 수 있어야 한다는 뜻이다..

[0] [2, 11, 14, 17, 21] [25] / n = 2
  [ 2, 9, 3, 3, 4, 3 ]

시작점과 첫번째 바위의 간격이 2이고 이는 10보다 작으니깐 첫 번째 바위를 삭제할 것이다.

[0] [0, 11, 14, 17, 21] [25] / n = 2
  [ 0, 11, 3, 3, 4, 3 ]
numRemove: 1

두 번째 바위와 세 번째 바위의 간격이 3이고 이는 10보다 작으니깐 세 번째 바위를 삭제해보자.

[0] [0, 11, 11, 17, 21] [25] / n = 2
  [ 0, 11, 0, 6, 4, 3 ]
numRemove: 2

이미 두번의 바위를 모두 삭제했음에도 10보다 간격이 작은 바위들이 존재한다. 즉, 10은 최솟값으로 적절하지 않다는 뜻이다. 이런 경우 탐색 값을 낮춰야 한다.

 

반대로 최솟값이 2인 경우의 유효성 검사를 해보자.

[0] [2, 11, 14, 17, 21] [25] / n = 2
  [ 2, 9, 3, 3, 4, 3 ]
numRemove: 0

바위를 하나도 삭제하지 않았는데 이미 조건을 만족한다. 바위를 삭제하게되면 최솟값을 더욱 높일 수 있다. 그렇기 때문에 2번의 기회를 사용하지 않는 것은 최솟값을 더욱 높일 수 있는 가능성이 남았다는 뜻이다. 그래서 더 높은 값을 탐색해보는 것이 좋을 것 같다. 이러한 유효성 검사를 가능한 모든 범위에서 진행해야 한다. 가능한 범위는 1부터 시작해서 최대 거리인 1,000,000,000이다. 우리는 1 ~ 1,000,000,000 사이를 이분 탐색을 통해서 유효한 값들 중 최댓값을 구할 수 있다.

 

이 방법의 시간복잡도를 따져보자. 우리는 1 ~ 1,000,000,000 사이를 이분 탐색해야 한다. 그리고 각 탐색마다 모든 최대 50,000개의 바위를 순회하면서 이 바위를 삭제할지 말지 판단해야 한다. 결국 바위를 삭제할지 말지 판단하는 코드가 핵심이다. 거리의 최댓값을 \(D_{Max}\), 바위의 개수를 \(N_r\)이라고 했을 때 시간 복잡도는 \(O(N_rlogD_{Max})\) 가 된다. 즉 최악의 경우에도 대략 \(50,000 * log (1,000,000,000) \doteqdot 50,0000 * 29.90)\ 회 정도의 연산으로 원하는 값을 구할 수 있기 때문에 무리 없이 사용할 수 있다.

구현

주어진 바위의 간격은 정렬이 되어있지 않기 때문에 거리를 기준으로 정렬을 먼저 해준 후 앞서 언급한 이분탐색을 진행한다. 그리고 유효성 검사를 진행할 때 바위를 삭제하면 이전 바위와의 간격을 그대로 누적시키기 위해서 gap이라는 변수를 사용했음에 유의하자.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    sort(rocks.begin(), rocks.end());
    rocks.push_back(distance);

    int left = 1;
    int right = distance;
    int mid = 0;
    int numRemove = 0;

    while(left <= right)
    {
        // 바위를 제거했을 경우의 거리를 측정하기 위해 바위에서 바위 사이의 거리를 저장할 변수
        int gap = 0;
        // mid값과 numRemove값 초기화
        mid = (left + right) / 2;
        numRemove = 0;

        // mid값의 유효성 검사
        // 시작점과 첫번째 바위의 유효성검사
        if(rocks[0] < mid)
        {
            numRemove++;
            gap += rocks[0];
        }
        else
        {
            gap = 0;
        }

        // i번째 바위와 i+1번째 바위의 유효성 검사
        for(int i = 0; i < rocks.size() - 1; i++)
        {
            if(rocks[i + 1] - rocks[i] + gap < mid) 
            {
                numRemove++;
                gap += rocks[i+1] - rocks[i];
            }
            else
            {
                gap = 0;
            }

            if(numRemove > n)
                break;
        }
       // 삭제 가능한 바위 개수가 남는다면, 거리를 늘린다. (left 값을 mid+1로 올린다.)
        if(numRemove <= n)
        {
            answer = mid;
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return answer;
}