이분탐색 > 징검다리 (Level 4)

문제 링크

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

프로그래머스

 

 

문제 설명

출발지점부터 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 이상 바위의 개수 이하입니다.

 

입출력 예

 

입출력 예 설명

문제에 나온 예와 같습니다.

 

소스코드

#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() );
	rocks.emplace_back( distance ); // 마지막 돌 ~ 맨 끝 거리 검사

	while( left <= right )
	{
		int maximum = ( left + right ) / 2; 
		int prev = 0; // 이전 돌의 위치
		int cnt = 0; // 제거 할 돌의 수
		for( int i = 0; i < rocks.size(); ++i )
		{
			if( rocks[ i ] - prev < maximum )// 현재 최대 값보다 큰 경우
				cnt++; // 현재 돌 삭제
			else
				prev = rocks[ i ]; // 돌 이동
		}

		if( cnt <= n )
		{
			answer = max( answer, maximum );
			left = maximum + 1;
		}
		else
		{
			right = maximum - 1;
		}
	}

	return answer;
}

 

생각해 볼 것

2시간 이상 고민해도 답이 안보여서 검색했더니, 이분탐색뿐만 아니라 파라매트릭 서치라는 것도 알아야 쉽게 푼다고 한다.  파라매트릭 서치란 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것이라고 한다.

이 문제는 돌을 빼서 최솟값 중 최댓값을 구하는 방식이 아닌, 각 지점 사이의 최댓값을 구하고, 이떄 돌이 제거된 수를 계산한다는 방식이다. 또한 문제에서 돌을 n개를 뺀다고 설명되어 있지만, n개 이하의 돌을 빼는 문제라고 한다.