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

문제

프로그래머스 이분탐색 - 징검다리 (Level 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 이상 바위의 개수 이하입니다.

입출력 예

distance	rocks	n	return
25	[2, 14, 11, 21, 17]	2	4

 

---

문제 풀이

접근 방식

바위 n개를 제거하여 각 지점 사이의 거리의 최솟값 중 가장 큰 값을 구하는 문제이다.

이 문제를 처음에는 그리디 방식으로 풀어보려고 하였으나, 규칙을 찾기가 어려웠다.

그래서 이 문제의 유형인 이분탐색으로 풀어야 하는 문제라고 판단하여 이분탐색으로 문제를 해결하였다.

 

우선, 각 바위들 사이의 간격을 gap 벡터에 저장해주었다.

그리고 low를 1, high를 distance로 설정하여 이분탐색을 수행하였다.

이분탐색은 mid를 바위들 사이의 최소 간격으로 설정하고, 이 간격이 가능한지 판단하는 방식으로 구현하였다.

판단은 최소 간격이 mid가 되기 위해 제거해야 하는 바위의 수(count)를 구하고, 이 수를 n과 비교하여 수행하였다.

 

count가 n보다 큰 경우는 불가능한 경우이기 때문에 high를 mid - 1로 설정해주었고,

그렇지 않은 경우에는 low를 mid로 설정해주었다.

low와 high가 같아질 때까지 이분탐색을 수행하여 답을 구하였다.

 

---

풀이 코드 - C++

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int len = rocks.size();
    if(len == n)
        return distance;
    
    sort(rocks.begin(), rocks.end());
    vector<int> gap;
    int start = 0;
    for(int i = 0; i < len; i++){
        gap.push_back(rocks[i] - start);
        start = rocks[i];
    }
    gap.push_back(distance - start);
    
    int low = 1;
    int high = distance;
    while(low < high){
        int mid = (low + high + 1) / 2;
        int count = 0;
        int prev = 0;
        for(int i = 0; i < len + 1; i++){
            if(mid <= gap[i] + prev){
                prev = 0;
            }
            else{
                count++;
                prev += gap[i];
            }
        }
        if(count > n)
            high = mid - 1;
        else
            low = mid;
    }
    return low;
}

실행 결과

실행 결과 : 100.0