문제

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

---

입력

• 출발지점부터 도착지점까지의 거리 distance
• 바위들이 있는 위치를 담은 배열 rocks
• 제거할 바위의 수 n

---

출력

바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값

---

풀이

제한조건

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

접근방법

접근1. 이분탐색 O
조건에서 주어지는 distance가 최대 10억이다.
O(N)에 수행되어도 약 10초라고 생각할 수 있다.
시간초과 100%

O(logN)수준으로 줄여야 하는데, 이분 탐색으로 접근할 수 있다.

여기서 문제가 되는것은 무엇을 기준으로 이분탐색을 하는가? 인데..

최소 M만큼의 거리를 만족하는 돌을 남겨두고 모조리 제거 해보면서, 돌의 개수에 따라, 조정한다.

int mid = (left + right) / 2;
int dist = Integer.MAX_VALUE;
int current = 0, removeCount = 0;
            
	for (int point : points) {
		int diff = point - current;
 		// 중간보다 왼쪽에 있는것은 출발지와 비교.
        if (diff < mid) {
        	removeCount++;
        } else { // 중간보다 오른쪽에 있는것은 가장 중간에 가까운것과 비교.
            current = point;
            dist = Math.min(dist, diff);
        }
}
            
            // 삭제된 돌의 수가 더 많다면, 범위를 좁혀 돌을 덜 제거해야 한다.
            if (removeCount > n) {
                right = mid - 1;
            } else {
                answer = dist;
                left = mid + 1;
            }

이분탐색을 통해, 적당한 거리를 찾고, 제거해야할 돌의 수를 만족한다면,
정답을 만족하는 시점이다.

---

코드

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);
        int[] points = new int[rocks.length + 1];
        for (int i = 0; i < rocks.length; i++) {
            points[i] = rocks[i];
        }
        points[rocks.length] = distance;
        
        int left = 0;
        int right = distance;
        int answer = 0;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            int dist = Integer.MAX_VALUE;
            int current = 0, removeCount = 0;
            
            for (int point : points) {
                int diff = point - current;
                // 중간보다 왼쪽에 있는것은 출발지와 비교.
                if (diff < mid) {
                    removeCount++;
                } else { // 중간보다 오른쪽에 있는것은 가장 중간에 가까운것과 비교.
                    current = point;
                    dist = Math.min(dist, diff);
                }
            }
            
            // 삭제된 돌의 수가 더 많다면, 범위를 좁혀 돌을 덜 제거해야 한다.
            if (removeCount > n) {
                right = mid - 1;
            } else {
                answer = dist;
                left = mid + 1;
            }
        }
        
        return answer;
    }
}