[프로그래머스] 징검다리 (이분탐색)

문제 소개

 

오늘 풀었던 프로그래머스 - 징검다리 문제를 정리합니다.

이 문제는 출발지점부터 도착지점까지 가는 경로 중,
바위를 n개 제거하여 "각 지점 사이의 거리의 최솟값"을 최대화하는 문제입니다.

문제 링크: 징검다리 - 프로그래머스

 

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. "거리의 최솟값"이 얼마나 될 수 있는지를 이분 탐색합니다.
2. 특정 거리(mid)를 기준으로, 이 거리보다 짧은 구간이 생기지 않도록 하려면 몇 개의 바위를 제거해야 하는지 계산합니다.
3. 제거해야 하는 바위 수가 n개 이하이면 거리를 늘리고, 초과하면 줄입니다.

---

해결 과정 및 코드

핵심 아이디어

1. 거리의 최소 후보값을 mid로 잡고,
2. rocks 배열을 순회하면서:
   • 현재 위치와 이전 위치 차이가 mid보다 작으면 바위를 제거
   • 그렇지 않으면 그 바위를 유지
3. 총 제거한 바위 수를 보고 n과 비교하여 이분 탐색 방향을 결정합니다.
4. 탐욕적(greedy) 방법과 결합된다
   rocks를 순회하면서, 거리 조건을 만족하지 못하는 바위는 즉시 제거한다.
5. 마지막 도착지점까지의 거리를 따로 체크해야 한다. (중간에만 보는 것 ×)

코드

시간 복잡도 : O(log(distance) × rocks.length)

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);
        int left = 1;
        int right = distance;
        int answer = 0;

        while (left <= right) {
            int mid = (left + right) / 2;
            int prev = 0;
            int removed = 0;

            for (int rock : rocks) {
                if (rock - prev < mid) {
                    removed++; // 거리가 짧으면 바위 제거
                } else {
                    prev = rock; // 거리 충분하면 바위 유지
                }
            }

            if (distance - prev < mid) removed++; // 마지막 도착점까지 거리 체크

            if (removed <= n) {
                answer = mid;
                left = mid + 1; // 거리를 늘려본다
            } else {
                right = mid - 1; // 거리를 줄인다
            }
        }

        return answer;
    }
}