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

코딩테스트 고득점 Kit > 이분탐색

징검다리 | 문제 바로가기

문제풀이 (2022-02-27 SUN 💻)

🤔 사담

이분탐색으로 분류된 두 문제 모두 어려웠다 😥
개념 자체는 익숙하지만 문제 풀면서 잘 활용해보지 않아서 그런 것 같다...
이번 문제도 이분탐색이든, 뭔가 다른 방법이든,
도저히 나지 않아 구글링의 도움을 받았다

⭐ 풀이의 핵심

처음에는 출발지점(0)과 도착지점(distance) 사이의 중간값 (아래 코드에서 mid 변수 값) 을 구하여
해당 값을 일종의 목표 최솟값으로 상정한다
즉, mid 값이 최솟값이 될 수 있도록,
mid 값보다 같거나 큰 거리들만 존재할 수 있도록 바위들을 제거!
해나가는 일종의 역발상적인 접근인 것이다

문제) 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 이므로

• 제거해야하는 바위 개수가 n보다 작거나 같을 경우
  (거리의 최솟값을 mid값으로 맞출 수 있다는 뜻이므로)
  answer를 mid 값으로 업데이트 해주고
  현재의 mid 값보다 큰 값들에 대해 이분탐색을 계속해나간다
• 반대의 경우에는
  현재의 mid 값보다 작은 값들에 대해 이분탐색을 계속해나간다

🔽 코드 (C++)

#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()); // 오름차순 정렬
    int start = 0;
    int end = distance;
    
    while (start <= end) {
        int mid = (start + end) / 2; // 목표로 잡은 거리의 최솟값
        
        // 상정한 목표 최솟값(mid)보다 짧은 거리가 가능할 경우 바위 제거
        int adj = 0;
        int cnt = 0;
        int size = rocks.size();
        for (int i=0; i<size; i++) {
            // 출발지점~바위 또는 바위~바위 간 거리 체크
            if (rocks[i] - adj < mid) { // 바위 제거 O
                cnt++;
            }
            else { // 바위 제거 X
                adj = rocks[i]; // 인접한 바위를 현재 바위로 업데이트
            }
        }
        // 마지막 바위~도착지점 간 거리 체크
        if (distance - adj < mid) {
            cnt++;
        }
        
        if (cnt <= n) { // 거리의 최솟값을 mid로 맞출 수 있는 경우
            // cf) 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return
            if (mid > answer) {
                answer = mid;
            }
            start = mid + 1;
        }
        else { // 거리의 최솟값을 mid로 맞출 수 없는 경우 
            end = mid - 1;
        }
    }
    
    return answer;
}