프로그래머스 징검다리(lv.4) 문제풀이

문제

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

제거한 바위의 위치각 바위 사이의 거리거리의 최솟값

[21, 17]	[2, 9, 3, 11]	2
[2, 21]	[11, 3, 3, 8]	3
[2, 11]	[14, 3, 4, 4]	3
[11, 21]	[2, 12, 3, 8]	2
[2, 14]	[11, 6, 4, 4]	4

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

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

제한사항

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

입출력 예

distancerocksnreturn

25

[2, 14, 11, 21, 17]

2

4

입출력 예 설명

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

 

해설

바위 n개를 제거해 바위 사이의 거리를 최대한 벌려야 한다. 문제는 브루트포싱(완전탐색)으로 바위 사이의 최소 거리를 모두 구해 비교한다면 시간이 많이 걸린다는 것이다. 이럴 때는 수많은 경우의 수에 집중하는 것이 아니라 거리에 집중하면 쉽게 문제를 풀 수 있다. 즉, 임의의 거리 d가 바위 n개를 제거해서 나올 수 있는 최소 거리 중 가장 큰 숫자인지를 증명하면면 되는 것이다.

 증명하는 방법은 다음과 같다. 기준점과 바위 사이의 거리가 distance보다 작으면 그 바위를 제거해 removed로 카운트하고, 크면 기준점을 해당 바위로 다시 잡고서 다음 바위와 거리를 다시 비교한 후, 제거한 바위의 갯수 removed이 n이면서 다른 removed와 n이 동일한 경우 중 d가 제일 큰 경우를 반환하면 된다.

 이 방법은 이진탐색 알고리즘으로 구현할 수 있다. 아래는 구현하는 방법에 대한 자세한 설명이다.

1. 먼저 최소거리 1을 left로, 최대 거리 distance를 right로 설정한다.

2. left와 right의 중간값을 mid로 설정한다. 우리는 mid가 바위 n개를 제거해서 나올 수 있는 최소 거리 중 하나인지 증명해야 한다. 증명이 된다면 mid는 정답 후보가 될 것이다.

3. 첫 기준점인 시작점 prev와 바위의 거리를 비교한다. mid보다 바위와 prev 사이의 거리가 짧다면 해당 바위를 삭제해야 mid가 최소 거리인 것이므로 삭제 카운트 removed를 +1한다.

4. 만약 mid보다 거리가 멀다면 해당 바위를 다시 기준점 prev로 잡고서 다른 바위와의 거리를 mid와 다시 비교한다. 거리가 짧으면 삭제 카운트 removed +1, 멀면 새로운 기준점으로 바위를 잡는다. prev가 되는 바위의 왼편은 자연스럽게 모두 검사되므로, 오른쪽 바위와의 거리만 비교하면 된다.

5-1. 삭제 카운트 removed가 삭제할 바위의 수 n보다 크다면 mid을 최소 거리로 만들기 위해서는 더 많은 바위를 삭제해야 한다는 뜻이다. 더 짧은 거리를 mid로 설정해야만 n보다 같거나 작은 수의 바위를 지워 mid를 최소 거리로 만들 수 있으므로 right의 값을 줄인 다음 2번부터 다시 반복한다.

5-2. 삭제 카운트 removed가 삭제할 바위의 수 n와 같거나 작다면 mid를 최소 거리로 만들기에 삭제 횟수 n회는 충분하다는 뜻이다. mid를 더 먼 거리로 설정해도 n회 만큼만  바위를 삭제해 mid를 최소거리로 만들 수 있는지 검사해볼 필요가 있다. 모든 검사를 끝내기 전까지는 현재의 mid 값이 가장 큰 최소값이기 때문에 answer에 따로 저장한다. left의 값을 늘린 다음 2번부터 다시 반복한다.

6. 만약 left의 값이 right보다 커지는 순간이 된다면 모든 검사가 끝난 것이므로 5-2에서 저장한 answer 값이 정답이다.

 

정답코드

#include <vector>
#include <algorithm>

using namespace std;

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

    int left = 1, right = distance;
    int answer = 0;

    while (left <= right) {
        int mid = (left + right) / 2;
        int prev = 0;
        int removed = 0;

        for (int rock : rocks) {
            if (rock - prev < mid) {
                removed++;
            } else {
                prev = rock;
            }
        }

        if (removed > n) {
            right = mid - 1;
        } else {
            answer = mid;
            left = mid + 1;
        }
    }

    return answer;
}