[Programmers Lv.4][징검다리][java]

문제 링크

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

프로그래머스

---

조건

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

 

알고리즘 

바위 간의 거리의 최솟값이 x라고 할 때 바위를 몇 개 제거되어야 하는지

최소 거리 기준치 mid 를 정해놓고 mid 를 보다 크면 제거

제거한 돌이 n 보다 크다? 그럼 최소 거리 기준이 아닌 것 → 최소 거리를 줄인다

n 보다 작다? 일단 최소 거리는 될 수 있는 것 → answer와 비교해서 큰 값을 저장 (최소 거리들 중에 최댓값을 찾는 것이기 때문에)

 

전체 코드

package com.example.javaproject3.psstudy;

import java.util.Arrays;

public class Solution43236 {
    public int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);  // 정렬
        long left = 1, right = distance;
        int answer=0;

        while (left <= right) {
            long mid = (left + right) / 2; // 기준
            int remove = 0, before = 0;  // remove: 제거하는 돌 개수, before: 이전 돌 위치 값

            for (int rock : rocks) {
                if ((rock - before) < mid) remove++; // (현재 돌-이전 돌) 이 최소 거리 기준치인 mid 보다 작으면 제거
                else before = rock;  // 돌이 제거되지 않을 때 이전의 돌 위치 변경해줌
            }
            if((distance - before) < mid) remove++;  // 마지막 돌이 before에 저장되어 있기 때문에 마지막 돌도 제거할 돌인지 확인

            if (remove > n)  right = mid - 1;  // 제거한 돌 개수가 n보다 크면 mid 는 최소 거리 기준이 아닌 것, 범위를 줄여야 함
            else { // n보다 작으면, 일단 최소 거리는 될 수 있음 
                answer = Math.max(answer, (int) mid);  //  answer와 mid 중 최댓값을 answer에 저장
                left = mid + 1; // 최소 거리를 늘려줌
            }
        }

        return answer;
    }
}