프로그래머스 징검다리 (C++)

프로그래머스

각 바위의 위치를 담은 배열과 목적지의 위치, 제거해야할 바위의 수를 입력받습니다. 이 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최소값 중에 가장 큰 값을 구해주세요.

 

풀이 방법

이진탐색으로 풀이하는 문제입니다. 탐색의 기준은 [바위 사이의 거리]입니다.

 

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

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

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

입력받은 배열은 정렬되어 있지 않기 때문에 sort 함수로 정렬을 해줍니다.

이후 0 ~ 목적지 까지 이분탐색을 사용합니다.

탐색의 기준인 [바위 사이의 거리]는 mid가 됩니다.

 

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

// prev -> 목적지도 계산에 포함
if (distance - prev < mid)
    remove_cnt++;

바위 사이의 거리가 mid보다 작다면 제거, 

그렇지 않다면 즉, 제거되지 않는다면 prev를 재설정 해줍니다.

 

 

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

제거한 바위의 수가 n보다 작거나 같다면 기준 거리를 늘려주고,

n보다 많이 제거 했다면 기준 거리를 줄여줍니다.

 

 

입력값이 [2, 11, 14, 17, 21], distance = 25일 때는 아래와 같이 동작합니다.

첫번째 사이클 :

2 - 0 = 2 < 12 → 제거 (remove_count = 1)
11 - 0 = 11 < 12 → 제거 (remove_count = 2)
14 - 0 = 14 ≥ 12 → 유지 (prev = 14)
17 - 14 = 3 < 12 → 제거 (remove_count = 3)
21 - 14 = 7 < 12 → 제거 (remove_count = 4)

도착지점 거리: 25 - 21 = 4 < 12 → 제거 (remove_count = 5)
결과: remove_count = 5 > n(2) → right = 11

 

두번째 사이클 :

2 - 0 = 2 < 5 → 제거 (remove_count = 1).
11 - 0 = 11 ≥ 5 → 유지 (prev = 11).
14 - 11 = 3 < 5 → 제거 (remove_count = 2).
17 - 11 = 6 ≥ 5 → 유지 (prev = 17).
21 - 17 = 4 < 5 → 제거 (remove_count = 3).

도착지점 거리: 25 - 21 = 4 < 5 → 제거 (remove_count = 4).
결과: remove_count = 4 > n(2) → right = 4.

 

세 번째 사이클 :

2 - 0 = 2 ≥ 2 → 유지 (prev = 2)
11 - 2 = 9 ≥ 2 → 유지 (prev = 11)
14 - 11 = 3 ≥ 2 → 유지 (prev = 14)
17 - 14 = 3 ≥ 2 → 유지 (prev = 17)
21 - 17 = 4 ≥ 2 → 유지 (prev = 21)

도착지점 거리: 25 - 21 = 4 ≥ 2 → 유지
결과: remove_count = 0 ≤ n(2) → answer = 2, left = 3

 

네 번째 사이클 :

2 - 0 = 2 < 3 → 제거 (remove_count = 1)
11 - 0 = 11 ≥ 3 → 유지 (prev = 11)
14 - 11 = 3 ≥ 3 → 유지 (prev = 14)
17 - 14 = 3 ≥ 3 → 유지 (prev = 17)
21 - 17 = 4 ≥ 3 → 유지 (prev = 21)

도착지점 거리: 25 - 21 = 4 ≥ 3 → 유지
결과: remove_count = 1 ≤ n(2) → answer = 3, left = 4

 

다섯 번째 사이클 :

2 - 0 = 2 < 4 → 제거 (remove_count = 1)
11 - 0 = 11 ≥ 4 → 유지 (prev = 11)
14 - 11 = 3 < 4 → 제거 (remove_count = 2)
17 - 11 = 6 ≥ 4 → 유지 (prev = 17)
21 - 17 = 4 ≥ 4 → 유지 (prev = 21)

도착지점 거리: 25 - 21 = 4 ≥ 4 → 유지
결과: remove_count = 2 ≤ n(2) → answer = 4, left = 5

- left = 5, right = 4 => 종료

 

 

정답 코드

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {

    sort(rocks.begin(), rocks.end());
    
    int answer = 0;
    int left = 0;
    int right = distance;
    
    while (left <= right)
    {
        int mid = (left + right)/2;
        int prev = 0;
        int remove_cnt = 0;
        
        for (int rock : rocks)
        {
            if (rock - prev < mid)
                remove_cnt++;
            else
                prev = rock;
        }
        
        if (distance - prev < mid)
            remove_cnt++;
        
        if (remove_cnt <= n)
        {
            answer = mid;
            left = mid +1;
        }
        else
            right = mid -1;
    }
    return answer;
}