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

 

문제 링크: programmers.co.kr/learn/courses/30/lessons/43236

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

 

풀이

 

이분 탐색으로 풀 아이디어가 도저히 안 떠올라서 다른 사람의 풀이를 참조해서 풀었다. (hyeon930님 풀이)

 

이분탐색으로 바위를 제거하는 것이 아니라, 이분 탐색을 이용해 각 지점 사이의 거리의 최댓값을 구해야 되는 문제였다. 문제를 다시 생각해보면, "각 지점 사이의 거리의 최솟값이 x가 될 수 있는가?"를 만족하는 x들 중에 최댓값을 찾는 것이다. 여기서 이 x를 이분탐색으로 범위를 좁혀가며 구하면 된다. 

 

이분 탐색을 위해, left = 0, right = distance로 초기값을 잡고 rocks는 오름차순으로 정렬(이분 탐색은 오름차순 정렬을 전제로 하므로)한다. 

이후 (left <= right) 조건을 만족하는 동안 다음을 반복한다. 

 

• mid(거리의 최솟값 x), prev(이전 바위의 위치), cnt(제거한 바위의 개수) 초기값 설정
• 모든 바위에 대해
  1) rocks[i] - prev < mid 일 경우
     이전 바위와의 거리가 mid보다 작으므로 현재 바위를 제거해야 함
  
  2) rocks[i] - prev >= mid 일 경우
     바위를 제거할 필요가 없으므로, 현재 바위가 다음 바위의 prev가 됨
• 마지막 바위와 도착지점까지의 거리에 대해서도 mid와 비교
• 1) cnt가 n보다 작으면 바위 사이의 거리의 최솟값이 mid가 될 수 있으므로, 다음 mid 값은 현재보다 크게 설정해야 한다. 
  2) 그렇지 않은 경우 mid 값을 줄여서 최댓값 x를 찾는다. 

 

 

 

소스코드

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    int left = 0, right = distance;
    sort(rocks.begin(), rocks.end());
 
    while(left <= right) {
        int mid = (left + right) / 2;
        int prev = 0, cnt = 0;
 
        for(int i = 0; i < rocks.size(); i++) {
            if(rocks[i] - prev < mid)   // rocks[i]를 제거해야 함
                cnt++;
            else
                prev = rocks[i];
        }
        if(distance - prev < mid)   // 마지막 바위와 도착지점까지의 거리 체크
            cnt++;
 
        if(cnt <= n) {  // 바위 사이 거리의 최솟값을 mid로 할 수 있을 경우
            answer = max(mid, answer);
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
 
    return answer;
}

 

테스트 결과