Programmers 64062: 징검다리 건너기

출발지점부터 distance 사이에 바위를 제거했을 때, 제거한 바위의 최솟값 중에 가장 큰 값을 구하는 문제이다.

이 문제는 바위를 제거하는 모든 경우를 구한 후 최솟값을 구한다면,

바위가 N개, R개를 제거할 수 있다면 O(NCR)로 시간초과가 발생하게 된다.

 

이러한 경우에는 바위를 제거하는 모든 경우의 수를 구하기보다는,

바위간의 최소 거리를 정해두고 이 조건이 가능한지 여부를 보는 쪽으로 생각하면 된다.

 

바위간의 최소 거리를 정할 때에는 이분 탐색을 사용하도록 했다. 풀이 방식은 아래와 같다.

1. 이분 탐색으로 최대 사잇값 diff를 정한다.

2. 돌을 n개 지웠을 때 최소 거리가 diff인지 확인한다.

=> 즉, 돌 사이의 거리가 diff보다 작으면 돌을 없애고,

최종적으로 없애야 하는 돌의 수가 n보다 크면 diff를 너무 크게 잡은 것이므로 왼쪽을 탐색하도록 한다.

class Solution {
	public int solution(int distance, int[] rocks, int n) {
		int length = rocks.length;
		int start = 0;
		int end = distance;

		int answer = 0;

		Arrays.sort(rocks);

		while (start <= end) {
			int mid = (start + end) / 2;
			if (!isPossible(rocks, n, length, mid, distance)) {
				// diff가 너무 크니까 줄이자
				end = mid - 1;
			} else { // 가능하니까 일단 answer에 저장하고 더 늘려보자
				answer = Math.max(answer, mid);
				start = mid + 1;
			}
		}
		return answer;
	}

	public boolean isPossible(int[] rocks, int n, int length, int diff, int distance) {
		int remove = 0;

		int before = 0;
		for (int i = 0; i < length; i++) {

			if (rocks[i] - before < diff) { // diff보다 작으니 돌을 없애자
				remove++;
			} else {
				before = rocks[i];
			}

			if (remove > n) { // 돌을 n개보다 더 없애야 하는 경우
				return false;
			}
		}

		if (distance - before < diff) {
			remove++;
		}
		return remove <= n;
	}
}