[99클럽 코테 스터디 14일차 TIL] 이분탐색

📖 오늘의 학습 키워드
이분탐색

오늘의 회고

문제

[징검다리]
https://school.programmers.co.kr/learn/courses/30/lessons/43236

나의 해결

import java.util.*;
class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int left = 1;
        int right = distance;
        Arrays.sort(rocks);
        while(left <= right) {
            int mid = (left + right) / 2;
            if(removeRocks(rocks, mid, distance) <= n) {
                answer = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return answer;
    }
    public int removeRocks(int[] rocks, int d, int end) {
        int count = 0;
        int previous = 0;
        for(int i = 0; i < rocks.length; i++) {
            if(rocks[i] - previous < d) {
                count++;
            }
            else {
                previous = rocks[i];
            }
        }
        if(end - previous < d) {
            count++;
        }
        return count;
    }
}

처음에 완전탐색을 떠올렸으나 바위 개수의 범위가 50,000개이하인 것을 보고 이분탐색을 떠올리게 되었다. 바위들 사이의 거리의 최솟값을 임의로 정한다. 그리고 이 값으로 정해지는 제거할 바위의 수와 n의 값을 비교하여 최솟값을 다시 구한다.

1. left는 1, right는 도착지점까지의 거리인 distance로 초기화한다. left와 right로 임의의 최솟값을 구한다.
2. 바위들이 있는 위치가 담긴 배열 rocks를 오름차순으로 정렬한다.
3. 이분탐색을 진행한다.
   1) 바위들 사이의 임의의 최소 거리인 mid를 left와 right의 절반값으로 구한다.
   2) mid값을 이용해 제거할 수 있는 돌의 개수를 구한다.
   3) rocks배열을 돌며 직전의 바위(previous)와 현재 바위 사이의 거리가 최소 거리보다 작다면, 삭제할 돌의 개수를 늘린다. 반대로 크거나 같다면 현재 바위의 위치로 직전 바위의 위치의 값을 갱신한다.
   4) for문이 끝나면 도착지점과 직전 바위의 거리를 구해 최소거리보다 작으면 제거할 바위의 개수를 하나 늘린다.
   5) 제거할 바위의 수가 n의 값보다 크다면 임의의 최솟값이 정답보다 크다는 소리이다. 간격이 클수록 제거할 돌의 개수도 많아질 수밖에 없기 때문이다. 따라서 right의 값을 mid보다 하나 줄인다.
   6) 반대로 제거할 바위의 수가 n의 값보다 작다면 임의의 최솟값이 정답보다 크다는 소리이다. 간격이 작으면 제거할 수 있는 돌의 개수가 작아지기 때문이다. 따라서 left의 값을 mid보다 하나 늘린다.
   7) n의 값과 제거할 바위의 수가 같다고 해서 바로 정답이라고 할 수 없다. 최솟값 중에 가장 큰 값을 반환해야 하기 때문이다. 그래서 6)번과 마찬가지로 left 값을 mid보다 하나 늘린다. 그리고 mid 값으로 answer를 갱신한다.

새로 학습한 내용