프로그래머스 문제 - 징검다리

프로그래머스 징검다리 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있으며 그 사이에 바위들이 놓여있습니다.
이 바위들을 몇 개 제거하려고 하는데 제거 후 출발지점, 도착지점, 바위 간의 거리의 최솟값 중 가장 큰 값을 찾을려고 합니다.
n개만큼 돌을 제거하였을때 최솟값 중 가장 큰 값을 구해야합니다.

문제 풀이

바위를 n개 제거하였을 때 각 바위 사이의 거리를 측정하여 나온 최소거리로 나올 수 있는 값들 중에서 가장 큰 값이 무엇인지를 물어보는 문제입니다.
이 문제는 이분탐색으로 해결이 가능한 문제인데, 이분탐색을 사용하기 위해서는 검색해야 하는 값을 하나 선택 후 값을 변경하며 값을 찾아야 합니다.
이 문제는 거리의 최솟값들 중 가장 큰 값을 찾는 것이므로 이를 중심으로 이분탐색을 돌려줍니다.

징검다리가 가질 수 있는 최대 거리는 distance와 같으므로 high는 출발지점에서 도착지점까지의 거리, low는 0으로 맞춘 후 이분탐색을 시작해줍니다.

n개의 돌을 제거했을 때 생기는 거리의 최솟값 중 가장 큰 값이므로 임의의 거리의 최솟값을 주었을 때 돌을 n개 이상 제거했다면 임의의 거리가 너무 크다는 뜻이고, n개보다 적게 제거했다면 거리가 적다는 뜻입니다.
mid를 거리의 최솟값일 경우로 생각했을 때 출발지점부터 오름차순으로 정렬 된 바위들을 앞에서부터 비교하여 mid보다 작다면 바위 제거, 크다면 출발지점을 갱신시키며 바위를 제거하게되는 수를 계산해줍니다.

high값이 low보다 커질 때까지 계산을 진행한 후의 값이 정답이 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    
    sort(rocks.begin(), rocks.end());
    int high = distance;
    int low = 0;
    //돌 사이의 거리를 중심으로 잡고 이분탐색 시작
    while(low <= high){
        int mid = (high+low)/2;
        int curRock = 0;
        int deleteRockCount = 0;
        //시작지점부터 돌까지의 거리 계산
        for(int i = 0; i < rocks.size(); i++)
        {
            if(rocks[i]-curRock >= mid){    //mid값보다 클 경우 새로 갱신
                curRock = rocks[i];
            }else{  //mid값보다 작을 경우 바위 제거
                deleteRockCount++;
            }
            if(deleteRockCount > n)
                break;
        }
        //도착지점까지와의 거리 계산
        if(distance-curRock >= mid){
            curRock = distance;
        }else{
            deleteRockCount++;
        }
        
        if(deleteRockCount > n)
            high = mid-1;
        else
            low = mid+1;
    }
    answer = high;
    
    return answer;
}

출저

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