[프로그래머스 LV4] 징검다리 (이진 탐색, 매개변수 탐색) [C++]

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

코딩테스트 연습 - 징검다리

징검다리가 주어지고, 출발지점과 도착지점 사이에 바위들이 놓여 있다.

바위들 중에서 n개를 지운 뒤, 바위들 간격의 최솟값을 만들 수 있는 경우 중 최댓값을 찾아내는 문제이다.

 

이 문제를 어떻게 이분 탐색으로 풀까 고민을 했다.

백준의 공유기 설치 문제와 비슷하다는 느낌을 받았다.

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

공유기 설치 문제 역시 N개를 설치해서 간격을 최대로 하는 값을 찾는다.

차이점은 N개를 설치하는가, N개를 지우는가

 

최종적으로, 이분 탐색으로 얻어내고자 하는 값은 간격의 최솟값 중 최댓값이며

처음 범위는 출발 지점인 0부터 도착 지점인 distance까지 정해주었다.

그리면 mid값이 현재 계산하는 값이며, mid를 통해 징검다리에서 간격의 개수를 세준다.

징검다리는 정렬을 한 상태이고, 0 2 11 14 17 21 25이고 처음 mid값이 12라면

0~14, 14~25 두 경우 밖에 돌다리를 선택할 수 없다.

 

이 케이스는 결국, 돌다리 2 11 14 17 21 중 2 11 17 21을 지운 결과이며

n = 2개를 지운 징검다리에서의 최솟값을 구해야 하지만 4개나 지웠으므로 mid(간격)을 줄여준다.

 

그래서 돌을 지운 개수가 n보다 크면 end = mid -1, 작거나 같다면 start = mid + 1으로 세팅을 해주었다.

돌을 지운 개수가 같다면 그 경우 중 최댓값을 찾아야 하므로 start를 키워주는 방향으로 했다.

 

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    rocks.push_back(distance); // 계산의 편의를 위해 distance push
    sort(rocks.begin(), rocks.end()); // 정렬
    
    int start = 0, end = distance;
    while(start <= end){
        int mid = (start + end)/2;
        int fix = 0;
        int cnt = 0;
        for(int i = 0 ; i < rocks.size() ; i++){
            int diff = rocks[i] - fix; // 바위끼리 간격
            if(diff >= mid){
                cnt++;
                fix = rocks[i]; // 간격이 갱신될때 기준 바위를 바꿔준다.
            }
        }
        if(rocks.size() - cnt > n){ // n개 지워도 mid가 거리의 최솟값 중 최대가 될 수 없음.
            end = mid-1; // mid를 더 줄여야한다.
        }
        else // n과 같은 경우 그 경우 중 최대를 찾아야하므로 값을 키워준다.
            start = mid + 1; // 최솟값을 늘려보자.
    }
    answer = end;
    return answer;
}