징검다리

문제 설명

출발지점부터 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

---

첫 시도

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    map<int, vector<int*>> distMap;

    rocks.emplace_back(0);
    rocks.emplace_back(distance);

    sort(rocks.begin(), rocks.end());

    for(int i = 1; i < rocks.size(); i++) {
        distMap[rocks[i] - rocks[i-1]].push_back(&rocks[i-1]);
        distMap[rocks[i] - rocks[i-1]].push_back(&rocks[i]);
    }

    for(auto& Drocks : distMap) {
        for(int j = 1; j < Drocks.second.size(); j += 2) {
            *Drocks.second[j] = -1;
            n--;
            if(n <= 0) {
                break;
            }
        }
        if(n <= 0) {
            break;
        }
    }

    vector<int> newRocks;
    for(int i : rocks) {
        if(i != -1) {
            newRocks.push_back(i);
        }
    }

    distMap.clear();
    rocks = newRocks;

    for(int i = 1; i < rocks.size(); i++) {
        distMap[rocks[i] - rocks[i-1]].push_back(&rocks[i-1]);
        distMap[rocks[i] - rocks[i-1]].push_back(&rocks[i]);
    }

    return distMap.begin()->first;
}

실패

그냥, 최소거리값을 map으로 가져온다음, 정렬한 뒤 가장 작은 거리들을 하나씩 제거하고.

다시 map을 재정렬 한 다음. 가장 작은 map의 distance값을 반환하면 될 줄 알았는데 실패함.

---

두 번째 시도

#include <algorithm>
#include <vector>

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    sort(rocks.begin(), rocks.end()); // 바위 위치 정렬
    rocks.push_back(distance); // 도착지를 마지막에 추가

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

    while (left <= right) {
        int mid = (left + right) / 2;
        int removedRocks = 0;
        int prevRock = 0;

        for (int i = 0; i < rocks.size(); i++) {
            if (rocks[i] - prevRock < mid) {
                // mid보다 작은 간격의 바위는 제거
                removedRocks++;
            } else {
                // mid 이상의 간격일 경우, 다음 비교를 위해 prevRock 갱신
                prevRock = rocks[i];
            }
        }

        if (removedRocks > n) {
            // 제거한 바위의 수가 n보다 크면 간격을 줄여야 함
            right = mid - 1;
        } else {
            // 제거한 바위의 수가 n 이하면 간격을 늘려도 됨
            left = mid + 1;
            answer = mid;
        }
    }

    return answer;
}

성공

 

정렬한다음, 객체를 중앙 좌측 우측으로 나눔

 

rocks를 순회하면서, prevRock을 확인. 기준점보다 적을경우 삭제하는것 으로 정의하고,

기준점보다 클 경우, 기준점을 갱신해줌.

 

그렇게 삭제되는 바위 개수를 계산하고, 개수가 n보다 크게 나왔다면, n개를 줄일때보다 현 간격이 크다는 것임으로 간격을 줄인다.

n보다 작다면, 설정된 간격이 n보다 간격이 크다는 의미 임으로, 간격을 늘린다.

 

그렇게 했을 때, 순환이 left와 right가 만났을 경우, 마지막으로 제거된 바위수가 n이하가 됨으로 distance값이 도출된다.