[프로그래머스] 징검다리 (Java, Parametric Search, lv4)

 

 

---

문제 출처 

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

프로그래머스

 

문제 풀이

- 처음 int[] rocks에서 n개의 바위를 제거하는 조합을 구하는 방식을 생각했으나 50,000C25,000으로 시간 초과 예상 

- 이진 탐색 중 매개변수 탐색으로 할 경우 N * log(1억) = 50,000 * 30 시간 복잡도로 풀이 가능

 

절차

- (중요*) int[] rocks를 오름차순 정렬 (ex. [2, 11, 14, 17, 21] )

- L과 R의 범위를 지정

- 바위 사이의 최소 거리(mid)를 정했을 때, 시작 지점에서 도착지까지 이동 가능한가 (이진 탐색으로 최대 log(1억) 소요)

- 바위 사이의 거리가 최소 거리(mid) 미만이라면 바위를 제거(removeCnt) 한다. (O(N) 시간 복잡도 소요)

- 그리고 제거한 바위 개수가 n 이하라면 답을 갱신하고 L을 증가 시킨다 

 

전체 코드 

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);
        
        int L = 0;
        int R = distance;    
        
        int answer = 0;
        while(L <= R) {
            int mid = (L + R) / 2; // 징검 다리 사이의 거리를 mid 로 했을 때 이동 가능한가 판별
            
            int removeCnt = 0;
            int cur = 0;
            for(int rock : rocks) {
                if(rock - cur < mid) removeCnt += 1;
                else cur = rock;
            }
            
            // 마지막 바위에서 도착지 (distance) 사이 거리가 mid 보다 작으면 removeCnt 증가
            if(distance - cur < mid) removeCnt += 1;
            
            // 바위 사이의 거리를 mid로 했을 때 최소 n개 이하의 바위를 제거하고 이동 가능한가
            if(removeCnt <= n) { 
                answer = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
            
        }
        
        return answer;
    }

}