[C++/PGS] Lv.4 : 징검다리 (이분탐색)

 

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

---

프로그래머스 레벨 4.

소요시간 약 50분

이진탐색을 활용하는 문제

 

어떤 값을 이분탐색으로 찾을 건지 결정하는게 가장 중요하다!!!

목표값만 찾으면 이제 로직은 어렵지 않은듯 ㅎ.ㅎ

 

이 징검다리 문제에서는 거리를 찾아야 하므로 (거리의 최솟값 중에 가장 큰 값)

1. left 시작점은 0, right 끝점은 distance로 두고

2. mid 값을 정답이라고 가정하면서

3. 이 때 제거해야 하는 돌의 수를 n과 비교한다.

4. 가능한 거리 값 중 최대값을 찾아야 하므로, 바위를 n개 이하로 제거하면 될 때의 mid 값을 저장한다.

5. 제거해야 하는 돌이 n보다 더 많다면, mid가 너무 큰 상황이므로 mid를 줄여야 함.

6. 제거할 돌이 n보다 적다면, mid가 작아서 널널한 상황이므로 늘려야 함

 

‼️ 4번 부연설명

if (removeCnt == n)이 아니라 if (removeCnt <= n)일 때, 답을 갱신해야 하는 이유!!!

바위를 딱 n개 제거할 수 있을 때만 정답 후보로 삼는다면,

더 큰 mid 값으로 n개 이하를 제거하는게 가능한 상황을 놓치게 됨 (우리의 목표는 mid의 최댓값이므로)

 

 

나의 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    sort(rocks.begin(), rocks.end());
    // 최소 거리 이분탐색, 거리가 mid보다 더 작으면 바위를 제거해야함
    // 제거해야 하는 바위의 수를 n과 비교하기
    int left = 0;
    int right = distance;
    int mid = (left+right)/2; // mid로 거리의 최솟값 중 최대값 찾기
    rocks.push_back(distance); // 도착 지점도 포함
    while(left<=right){
        int removeCnt = 0;
        // 제거할 바위 수 카운트
        int prev = 0; // 이전 위치를 기억
        for(int i=0; i<rocks.size(); ++i){
            if(rocks[i]-prev < mid){ // 제거하면 이전 위치는 그대로.
                removeCnt++;
            }
            else prev = rocks[i]; // 제거하지 않으면, 이전 위치를 현재위치로 갱신
        }
        if(removeCnt<=n) {
            if(answer<mid) answer = mid;
        }
        // 제거할 수가 적으면, 최솟값을 늘리기
        if(removeCnt <= n) left = mid+1;
        else right = mid-1;
        mid = (left+right)/2;
    }
    return answer;
}