[JAVA] 프로그래머스 연습 징검다리

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

프로그래머스

 

접근 : 

 

 - 이분 탐색을 사용

 

 - 징검다리에서 정답이 되는 값을 넣어서 빼낸 돌의 갯수가 n개인지 확인

 

 - 빼낸 돌의 갯수가 많다면 예상 정답 값을 내리고, 빼낸 돌의 갯수가 적다면 정답의 값을 올린 후 계속 탐색 진행

 

 - 정답에 도착하면 while 문을 탈출하므로 마지막 값을 정답으로 갱신한 후 출력

 

 

 

코드구현 : 

 

import java.util.*;

class Solution {

    // 돌 사이의 간격이 target 보다 작은 경우 제거
    private int removeRock(int[] rocks, int target){
        int prev = 0;
        int count = 0;

        for(int rock : rocks){
            if(rock - prev < target){
                count++;
                continue;
            }
            prev = rock;
        }
        return count;
    }

    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int left = 1;
        int right = distance;
        int mid = 0;
        int[] rock_dist = new int[rocks.length+1]; 
        for(int i = 0 ; i < rocks.length ; i++) rock_dist[i] = rocks[i];
        rock_dist[rocks.length] = distance;

        Arrays.sort(rock_dist);
            
        while(left <= right){
            mid = (left + right)/2;
            // 제거한 돌 갯수가 n 보다 많은 경우 mid를 오른쪽으로 이동 
            if(this.removeRock(rock_dist, mid) > n){
                right = mid-1;
                continue;
            }

            answer = mid;
            left = mid+1;
        }
        return answer;
    }
}