코딩테스트 -- 징검다리 - (프로그래머스 / C++)

프로그래머스

 

문제!

---

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치각 바위 사이의 거리거리의 최솟값

[21, 17]	[2, 9, 3, 11]	2
[2, 21]	[11, 3, 3, 8]	3
[2, 11]	[14, 3, 4, 4]	3
[11, 21]	[2, 12, 3, 8]	2
[2, 14]	[11, 6, 4, 4]	4

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

 

---

요약하면 징검다리에서 바위 n개를 없애버릴 예정인데  n개의 바위를 삭제 했다고 했을때

각 바위간의 거리의 최솟값들중 최댓값을 구하는 문제!

 

네... 일반적인 조합탐색을 하기에는 도착지점까지의 거리가 1,000,000,000 많이 머네요... 이때 사용하는 방법이 이분탐색!

 

하지만 어떻게 무엇을 이분탐색 해야할지 감이 오질 않아 찾아보았습니다.

 

 

일단 기본적으로 좌우 값을 설정해두고 정렬되어있지 않은 바위 배열을 정렬해줍시다.

int answer = 0;
    int left = 0;
    int right = distance;
    
    sort(rocks.begin(), rocks.end());

 

 

여기부터가 이분탐색 시작!

while(left <= right) {// 이분탐색 시작
        int mid = (left + right) / 2;
        int prev = 0;
        int cnt = 0;
 
        for(int i = 0; i < rocks.size(); i++) {// 한번 탐색
            if(rocks[i] - prev < mid){// 거리의 최솟값보다 작을때 >> 삭제
                cnt++;
            }
            else{// 크다면 그대로 이동
                prev = rocks[i];
            }
                
        }
        
        if(distance - prev < mid){// 마지막 바위와 도착지점
            cnt++;
        }

이분탐색으로 사용할 값은 현재 바위와 다음 바위간의  거리가 현재 mid값보다 작을때 삭제해주는 방식을 사용했습니다

 

>> 왜? >> 현재 최솟값이 mid로 설정 되어있기에 mid 값보다 짧은 거리를 가진 두 바위중 하나를 없애 거리를 늘려주는것!

 

이렇게 현재 mid 값에 따라 돌을 얼마나 제거해야하는지가 나오게됩니다!

 

 

그러면 아래처럼 n의 갯수와 비교하여  

n보다 많은 돌을 제거해버렸다?  >>  mid값을 낮춰야 한다 >> right = mid-1 

n보다 적은 돌을 제거해버렸다?  >> mid 값을 높여야 한다 >> left = mid +1 

if(cnt <= n){// 없애버린 바위의 갯수가 n보다 작을때
            answer = max(mid, answer); 
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }

 

이런식으로 적절값인 mid를 찾아주면 됩니다!

 

 

 

이분 탐색시에 이상한 점화식을 통한 mid 값도 있었지만

이번 문제에서는 그냥 값인 거리의 최솟값을 비교함으로써 값을 구할수있었습니다.

 

일단 범위가 무지막지한 문제가 나왔다?

일단 그 범위에 포함될수있는?  >> ex ) 거리랑 최단거리?   최대 갯수와 사야할 물건수? 등등

 

같은 종류의 어떤것을 이분탐색 하면 될것 같습니다....

 

아직은 익숙하진 않네요...

 

 

 

ALL

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    int left = 0;
    int right = distance;
    
    sort(rocks.begin(), rocks.end());
 
    while(left <= right) {// 이분탐색 시작
        int mid = (left + right) / 2;
        int prev = 0;
        int cnt = 0;
 
        for(int i = 0; i < rocks.size(); i++) {// 한번 탐색
            if(rocks[i] - prev < mid){// 거리의 최솟값보다 작을때 >> 삭제
                cnt++;
            }
            else{// 크다면 그대로 이동
                prev = rocks[i];
            }
                
        }
        
        if(distance - prev < mid){// 마지막 바위와 도착지점
            cnt++;
        }   
        
        
        if(cnt <= n){// 없애버린 바위의 갯수가 n보다 작을때
            answer = max(mid, answer); 
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
 
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!