[프로그래머스] 징검다리

아이디어

• 이분탐색을 사용할 줄 안다.

접근방식

1. 돌들의 위치를 sort를 이용해 오름차순으로 정렬한다
2. 이분탐색을 이용해서, 각 돌을 놓을 때 마다 가장 가까운 돌과의 거리를 mid와 비교, 만약 더 작다면 cnt(돌을 뺀 횟수)를 더해준다
3. 만약 cnt > n 일 경우 end = mid - 1로 목표 거리를 줄여준다
4. 만약 cnt <= n 일 경우 충분히 돌을 놓을 수 있으므로, start = mid + 1로 거리를 늘려준다.

#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;
        int cnt = 0;
        int left = 0;
        
        for(int i=0;i<rocks.size();i++){
            if(rocks[i] - left >= mid) left = rocks[i];
            else cnt++;
        }
        
        if(cnt > n) {
            end = mid - 1;
        }
        else{
            answer = max(answer,mid);
            start = mid + 1;
        }
    }
    
    return answer;
}

평가

이분탐색 - 파라매트릭 서치를 알면 5분, 모르면 1시간을 고민하는 문제.
요즘 코딩테스트, 코딩 챌린지 문제들을 풀면서 파라매트릭 서치에 관한 문제가 굉장히 많이 나왔습니다.
파라매트릭 서치는, 이분탐색인걸 깨닫고, 아이디어가 떠오른다면 구현자체가 정말 쉽기때문에, 굉장히 빠른시간 안에 코드를 짤 수 있지만,
이분탐색인걸 깨달아도, 아이디어를 못낸다면 몇시간이고 고민해야하는게 파라매트릭 서치 문제인것같습니다.
이분탐색 문제는 많이 경험해보는 수 밖에 없고, 범위가 엄청 크다면(특히 10억 이상) 이분탐색 및 파라매트릭서치인지 의심을 해봐야할 것 같습니다.