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

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

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

---

 

풀이

이분탐색으로 문제를 풀었다.

먼저 돌들이 순서대로 들어왔다는 보장이 없으므로, 정렬을 해준뒤, 마지막 도착지점도 돌을 놔준다.

그다음 이분탐색의 mid값을 돌다리 사이의 최소거리라고 생각을 하고, 돌들을 탐색하면서 이 최소거리로 건너뛸 수 있는 돌들을 체크해준다. 이 돌들이 제거하려는 돌보다 많다면, 간격을 줄이기 위해 right의 값을 갱신시켜주고, 돌들이 제거하려는 돌보다 적거나 같다면, 간격을 늘려주기 위해 left값을 갱신시켜주면된다.

 

시간복잡도

정렬에 O(NlogN)시간이 걸리며, 이분탐색으로 O(NlogN)이 걸리므로, 총 O(NlogN)이 된다

 

코드

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    rocks.push_back(distance);
    
    sort(rocks.begin(),rocks.end());
    
    int left=0;
    int right=1000000000;
    
    while(left<=right){
        int mid=(left+right)/2;
        int sum=0;
        int st=0;
        for(int i=0;i<rocks.size();i++){
            if(rocks[i]-st<mid){
                sum++;
            }
            else{
                st=rocks[i];
            }
        }
        
        if(sum>n){
            right=mid-1;
        }
        else{
            answer=mid;
            left=mid+1;
        }
    }
    return answer;
}