Programmers 43236: 징검다리

최소 거리를 구하는 방법보다는 최소 거리를 찍어놓고 그 거리가 가능한지 여부를 확인한다.

풀이 로직은 아래와 같다.

 

1. 이분탐색으로 가능한 거리 mid를 찍는다.

2. 없앨 돌의 수(remove)를 계산한다 - 돌 사이의 거리가 mid보다 짧으면 없애서 돌 사이의 거리를 늘린다.

3. 없앨 돌의 수가 n보다 큰 경우 돌 사이가 더 가깝다는 의미이므로 왼쪽탐색, n보다 작거나 같은 경우는 오른쪽을 탐색하면서 업데이트

import java.util.*;
import java.util.stream.Collectors;
class Solution {
	public int solution(int distance, int[] rocks, int n) {
		List<Integer> rock = Arrays.stream(rocks).boxed().collect(Collectors.toList());
		rock.add(0);
		rock.add(distance);
		Collections.sort(rock);

		int right = distance;
		int left = 0;
		int mid = 0;
		int answer = 0;

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

			int i = 0;
			int j = 1;
			while (i < rock.size() && j < rock.size()) {
				if (rock.get(j) - rock.get(i) < mid) {
					remove++;
					j++;
				} else {
					i = j;
					j++;
				}
				if (remove > n) {
					break;
				}
			}

			if (remove <= n) {
				left = mid + 1;
				answer = Math.max(answer, mid);
			} else {
				right = mid - 1;
			}

		}

		return answer;
	}
}