프로그래머스 징검다리

- 문제 설명

 

출발지점부터 distance 만큼 떨어진 도착지점이 있습니다. 그 사이에 바위 중 몇개를 제거했을 때 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 하는 solution 함수를 작성 

 

 

- 입력

 

1) 출발지점부터 도착지점까지의 거리 (1 <= distance <= 1,000,000,000)

2) 바위 (1 <= rocks <= 50,000)

3) 제거할 바위의 수 (1 <= n <= rocks)

 

 

- 출력

 

바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값

 

 

* 문제 풀이의 핵심

 

이 문제는 이분탐색으로 카테고리 되어 있습니다. 문제를 처음 봤을 때 무엇을 이분탐색 해야할지 알아내기 쉽지 않은 문제입니다. (이해하는데 참고한 사이트는 하단에 링크 표시하였습니다.)

 

 

1. 무엇을 이분탐색 할 것인가?

 

각 바위가 위치한 지점과 지점 사이의 최소 거리를 이분탐색 해야 합니다.

 

각 지점 사이의 최소 거리를 너무 길게 설정하면 돌을 너무 많이 제거하게 되고, 각 지점 사이의 최소 거리를 너무 짧게 설정하면 돌을 너무 적게 제거하게 되는 특징을 활용합니다.

 

그 과정에서 돌을 n개 제거했을 때 각 지점 사이의 최소 거리를 찾을 수 있습니다.

 

 

각 바위 사이의 최소거리에 따라 제거할 돌의 개수가 달라진다.

 

 

2. 알고리즘

 

무엇을 이분탐색 할지 정했다면, 돌을 어떻게 제거할지에 대해서 알아내셨다면 문제를 쉽게 해결 수 있습니다.

 

1) rocks 를 오름차순 정렬한다.

 

2) left, right 를 정의하고 이분탐색을 한다. right 는 최대거리인 INT_MAX 로 설정한다.

 

- prev : 이전에 선택한 바위로 시작점인 0 부터 시작한다.

- removedRocks : 제거한 바위의 개수로 left, right 값에 영향을 미친다.

- minValue : 구한 바위사의의 거리 중 최소값을 구한다.

 

 

3) rocks를 순회하면서 돌을 제거한다.

 

3-1) 바위사이의 최소거리가 mid 보다 작다면 돌을 제거한다. (rocks[i] - prev < mid)

 

3-2) 그렇지 않으면,

 

- 각 바위사이의 거리가 최소거리보다 크면서, 가장 작은 값을 구한다.

- 현재 바위를 이전에 선택한 바위로 갱신시킨다.

 

 

4) left, right 값을 갱신한다.

 

4-1) 제거한 바위의 개수가 n개 보다 많다면, 바위을 더 적게 제거해야 하므로 right = mid - 1; 이 된다.

 

4-2) 그렇지 않다면 left = mid + 1; 이 된다. answer 를 갱신한다.

 

 

- 소스코드

 

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
	int answer = 0;

	sort(rocks.begin(), rocks.end());

	int left = 0;
	int right = INT_MAX;

	while (left <= right) {
		int mid = (left + right) / 2;
		
		int prev = 0;
		int removedRocks = 0;

		int minValue = INT_MAX;

		int i;
		for (i = 0; i < rocks.size(); i++) {
			if ((rocks[i] - prev) < mid) {
				removedRocks++;
			}
			else {
				minValue = min(minValue, (rocks[i] - prev));
				prev = rocks[i];
			}
		}

		if (removedRocks > n) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
			answer = minValue;
		}
	}
	   
	return answer;
}

 

 

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

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

 

 

- 제출한 코드

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요

 

 

- 참고

1) 블로그 : m.post.naver.com/viewer/postView.nhn?volumeNo=27217004&memberNo=33264526