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

문제

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

프로그래머스

접근방법

이분탐색은 보통 정렬되어 있는 숫자를 이용한다.

 

이분탐색을 이용해 찾아야할 값은 뭘까? distance의 범위가 100,000,000까지였기 때문에,

distance를 가지고 이분탐색을 해야한다는 직감이 들었지만,

이분탐색으로 뭘 찾아야할 지, left와 right로 이동하는 기준이 뭐가 되야하는 지 알지 못했다.

 

결과적으로 여기서 이분탐색을 이용해 찾아야하는 숫자는 

거리의 최솟값 중 가장 큰 값이다.

 

distance까지의 숫자들을 이분 탐색해 거리의 최솟값 중 가장 큰 값을 찾아낸다.

그렇다면 좌측 우측을 선택하는 기준은 뭘까?

 

mid값이 정답이라는 가정 하에

바위 사이 거리 배열을 탐색하며 빼야하는 바위의 개수를 센다.

 

만약 mid가 13이라면, 

최솟값 중 가장 큰 값이 13이라는 뜻이므로,

바위 사이 거리 배열의 원소가 최솟값 13이 되도록, 바위를 하나씩 빼는 것이다.

만약, 최솟값 13을 맞추기 위해서 바위를 너무 많이 빼냈다면,

 

이번엔 7을 검사한다. 최솟값 7을 맞추기 위해서는 13보다는 바위를 적게 빼도 된다.

코드

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

int solution(int distance, vector<int> rocks, int n) {
    sort(rocks.begin(), rocks.end());
    int answer = 0;
    vector<int> dist;
    
    //바위 사이 거리 저장
    int l = 0;
    for (auto& r : rocks) {
        dist.push_back(r - l);
        l = r;
    }
    dist.push_back(distance - l);
    
    int left = 1;
    int right = distance + 1;       //만약 distance로 설정하는 경우, 절대 distance가 정답이 될 수 없기 때문에 + 1을 해줌.
    int mid;
    while(right - left > 1) {
        mid = (right + left) / 2;           //mid는 거리 사이 최솟값을 의미.
        int sum = 0;
        int removed = 0;
        for (int i=0;i<dist.size();i++) {
            sum += dist[i];
            if (sum >= mid) sum = 0;
            else removed++;
        }
        //removed가 n보다 크면 좌측으로 이동
        //mid가 left로 가면 무한루프를 돌게됨.
        //mid = (left + right) / 2 이기 때문.
        if (removed > n) right = mid;
        else left = mid;
    }
    answer = left;
    
    
    return answer;
}

개선할 점

이분탐색할 때, 주의할 점은

정답의 위치가 mid일 때, left = mid를 해주면 안된다.

right = mid를 해줘야한다.

이유는 mid = (left  + right) / 2이기 때문에,

left = 3, right = 4일 때,

mid의 값은 3이고, left = mid를 하면, 다시

left = 3, right = 4이기 때문에 무한 루프를 돌게 된다.

right = mid를 해주면

left = right = 3이다.

 

 

바위의 개수를 2개 빼야한다는 생각에 너무 매몰된나머지,

거리의 최솟값을 정해놓고, 바위를 그 값에 맞춰서 뺄 수 있다는 생각 자체를 못했다.

이분탐색에서 중요한 것은 이분탐색을 통해 찾을 숫자가 어떤 것인지를 찾는 건데,

이 숫자는 정답 그 자체가 될 수도 있고, 다른 숫자가 될 수도 있다.

 

다음부터는 문제에 제시되어 있는 값 중에서 하나씩 골라 하나씩 실험해봐야겠다.