[프로그래머스 알고리즘 고득점 Kit][이분탐색][Java] 징검다리

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

프로그래머스

https://www.acmicpc.net/problem/2110

백준의 공유기 설치와 동일한 문제
하지만 징검다리가 문제는 억지로 끼워맞춘 느낌이라 이해하기 쉽지 않았음

 

1. 정답 코드

문제를 조금 이해하기 쉽게 나의 언어로 바꿔 말한다면,

임의의 위치의 바위를 n개 부쉈을 때
시작점, 바위들, 도착지 사이의 거리들을 나열할 수 있다.
그 거리들 중에는 항상 최소가 되는 거리가 있는데,
이 문제는 그 최소 거리가 최대가 되게 만드는 문제다.

예를 들어,

출발지점 - 바위1 - 바위2 - 바위3 - 바위4 - 바위5 - 도착점

이렇게 있고, 5개 중 2개를 부숴서 거리를 구했을 때

• 1 111 222 333
• 3 4 5 6

이렇게 두 가지 경우만 나왔다고 가정하면,
각 경우의 최소값은 각각 1, 3이다.
우리는 이 최소값들 중 가장 큰 값을 찾아야 하므로 정답은 3이 된다.

 

그러면 우리는 최소 거리를 임의로 정했을 때,
그 값이 실제로 최소 거리로 가능하다면 최소 거리를 늘리고,
불가능하다면 줄이면서 계산하면
결국 최소의 최대를 구할 수 있다.

 

일단 최대 거리 distance가 10억이기 때문에
최소를 0부터 하나씩 늘려가면서 계산할 수는 없다.
그래서 이분 탐색을 떠올릴 수 있다.

한 번 검증할 때 바위들을 한 번 훑는다고 보면,
전체는 (거리 검증 횟수) * log distance 안에 끝낼 수 있다.

 

그러면 start를 출발지점인 0,
end를 도착지점인 distance로 두고 이분 탐색을 시작한다.

그리고 정답 후보인 mid를 매번 검증한다.

 

지금 이 mid가 최소 거리가 될 수 있는가를 검증하는
isMidMin 메서드를 보면 왼쪽부터 하나씩 비교하는데,
바위의 개수가 m개라고 하면 mCn으로 어떤 바위를 부술지 전부 비교하기에는
시간이 너무 많이 든다.

 

하지만 이 문제는 모든 경우의 수에서 정답을 직접 찾는 것이 아니라,
현재 mid가 가능한지 불가능한지만 판단하면 되는 문제다.
그래서 왼쪽부터 하나씩 비교해도 가능 여부를 판단할 수 있다.

 

 

왜 왼쪽부터 봐도 되냐면,
mid가 가능한지 보려면 지금 기준점에서 다음 지점까지의 거리만 확인하면 되기 때문이다.
가장 왼쪽에서 시작해서 오른쪽으로 가면서, 거리가 mid 이상이면 그 지점을 남기고 기준점을 옮긴다.
거리가 mid보다 작으면 그 지점은 남길 수 없으니 부수고 더 먼 곳을 본다.
이 과정을 끝까지 반복하면 mid를 만들기 위해 몇 개를 부숴야 하는지 알 수 있고, 그걸로 mid가 가능한지 판단할 수 있다.

그러면 로직을 좀 더 자세하게 설명하면

 

시작 지점부터 다음 지점(바위)들의 거리를 봤을 때
mid보다 거리가 작다면
현재 상태로는 최소 거리를 mid 이상으로 유지할 수 없으므로
그 바위를 부수고 계속 비교해본다.

반대로 그 거리가 mid보다 크거나 같다면
그 바위는 남길 수 있으므로
다음 지점으로 이동해서 다시 비교해본다.

이것을 반복해보면
mid를 최소 거리로 만들기 위해 부숴야 했던 바위의 개수를 셀 수 있다.

그리고 그 개수를 부술 수 있는 바위 개수 n과 비교한다.

• 부숴야 했던 바위의 개수가 n보다 크다면
  mid는 최소 거리가 될 수 없다.
  즉, mid가 너무 큰 값이라는 뜻이므로 mid 값을 줄여서
  가능한 지점을 찾을 때까지 반복한다.
• 부숴야 했던 바위의 개수가 n보다 작거나 같다면
  mid는 최소 거리가 될 수 있다.
  그러면 더 큰 최소 거리도 가능한지 확인하기 위해
  mid 값을 늘려서 더 큰 최소가 있는지 찾아본다.

이 과정을 반복하면
결국 가능한 최소 거리들 중 가장 큰 값을 구할 수 있다.

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);
        
        int start = 0;
        int end = distance;
        int answer = 0;
        while(start <= end) {
            int mid = (start + end)/2;
            
            if(isMidMin(rocks, mid, n, distance)) {
                answer = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        
        return answer;
    }
    public boolean isMidMin(int[] rocks, int mid, int n, int distance) {
        int curr = 0;
        int removed = 0;
        int rocksLength = rocks.length;
        for(int rock : rocks) {
            if(rock - curr < mid) {
                removed++;
            } else {
                curr = rock;
            }
        }
        if(distance - curr < mid) {
                removed++;
        }
        
        return removed <= n;
    }
}