프로그래머스 - 징검다리 - 이진탐색 - Java

1. 문제

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

2. 풀이

이진탐색의 🚨KeyPoint는

1. 어떤 값을 이진탐색 할것인가
2. lowerBound인가, upperBound인가 (즉 범위를 어떻게 세울 것인가)

문제를 보면 이게 이진탐색 문제인가? 싶기도 하다. 일단 제한 사항의 범위가 크면 무조건. 이진탐색을 의심해봐야한다.

도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.

각 지점 사이의 거리의 최솟값중에 가장 큰값이니 이 문제는 바위 사이 거리를 이분탐색 값으로 잡고 시작한다.

최소값 중에 최대값을 구하는 문제. 즉 UpperBound를 이용해서 문제를 푼다.
upperBound : 찾고자 하는 값(이상의)값이 처음으로 나타나는 위치를 사용한다.
참고 - upperBound
참고 - 공유기 설치

핵심 ✨Point

🚨🚨가장 중요한 점이 있는데 도착 지점과 마지막 바위 사이의 거리 또한 고려해야한다. 따라서 rocks 배열을 늘려 마지막 index에 distance값을 삽입해야 합니다.

rocks = Arrays.copyOf(rocks, rocks.length + 1);
rocks[rocks.length - 1] = distance;

1. start / end

   start = 1, end = distance + 1(upperBound이기 때문)

3. 코드

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        
        //가장 중요한 부분
        rocks = Arrays.copyOf(rocks, rocks.length + 1);
        rocks[rocks.length - 1] = distance;
        
        Arrays.sort(rocks);
        
        long start = 1;
        long end = (long) (distance + 1);
        
        while(start < end){
            long mid = (start + end) / 2;
            long current = 0;
            int count = 0;
            
            for(int i = 0; i < rocks.length; i++){
                if(rocks[i] - current >= mid){
                    current = rocks[i];
                    count++;
                }
            }
            
            if(count >= (rocks.length - n)){
                start = mid + 1;
            } else{
                end = mid;
            }
        }
        
        return (int)end - 1;
    }
}