[프로그래머스] 징검다리 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/43236?language=java# 

코딩테스트 연습 - 징검다리

 

풀이

아래 이분 탐색 문제와 동일한 유형의 문제이다. 

2021.11.29 - [Problem Solving/BOJ] - [BOJ 2110] 공유기 설치 (Java)

2021.12.01 - [Problem Solving/BOJ] - [BOJ 1654] 랜선 자르기 (Java)

2021.11.30 - [Problem Solving/BOJ] - [BOJ 2805] 나무 자르기 (Java)

 

지점 간 최소 거리를 이분 탐색하면서 최대 값을 찾는 것이 핵심이다. 아래와 같이 징검 다리가 있다. 

바위를 2개 파괴했을 때, 지점 간의 최소 거리의 최대 값을 찾아야 한다.

2번 바위와 14번 바위를 제거하면 거리의 최소값이 4가 된다.

이분 탐색으로 접근

지점 간 최소 거리를 이분 탐색을 해보자.

• 지점 간 최소 거리의 최소값 : 1
• 지점 간 최소 거리의 최대값: 25

 

첫 번째 탐색 

left : 1, right: 25, mid: 13

시작 ~ 2번 바위의 거리는 2이며, 13 보다 작다. 2번 바위 제거 

시작 ~ 4번 바위의 거리는 4이며, 13 보다 작다. 4번 바위 제거 

시작 ~ 11번 바위의 거리는 11이며, 13보다 작다. 11번 바위 제거 

시작 ~ 14번 바위의 거리는 14이며, 13보다 크다. 유지 

14번 ~ 17번 바위의 거리는 3이며, 13보다 작다. 17번 바위 제거 

14번 ~ 21번 바위의 거리는 7이며, 13보다 작다. 21번 바위 제거 

14번 ~ 도착지까지의 거리는 11이며, 13보다 작다. 14번 바위 제거

 

지점 간 최소거리를 13으로 가정하면, 총 6개의 바위가 제거 된다.

우리가 제거 해야할 바위는 2개이므로 최소 거리를 줄여서 재탐색 해야 한다.  

두 번째 탐색 

left : 1, right: 12, mid: 6

제거된 바위 4개

최소 거리를 줄여서 재탐색 

 

세 번째 탐색 

left: 1, right: 5, mid: 3 

제거된 바위 1개

최소거리 증가하여 재탐색

 

네 번째 탐색 

left: 4, right: 5, mid: 4 / answer = 4

다섯 번째 탐색 

left: 5, right: 5, mid: 5

제거 바위가 N개를 초과하므로 right = mid -1 이 되고 right가 left보다 작아지면서 while 문이 종료된다. 

가장 마지막에 갱신된 answer 값이 답이 된다.

 

소스코드

import java.util.*;
class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
    
        Arrays.sort(rocks);
        
        int left = 1;
        int right = distance;
        while(left <= right){
            int mid = (left + right)/2;
            if(getRemovedRockCnt(rocks, mid, distance) <= n){
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1; 
            }
        }
        
        return answer;
    }
    
    public int getRemovedRockCnt(int[] rocks, int mid, int distance){
        // mid가 바위(지점) 간 최소 거리가 되어야 함
        // 그렇게 하기 위해 제거 해야할 바위의 개수를 리턴한다. 
        int before = 0; 
        int end = distance;
        
        int removeCnt = 0;
        for(int i = 0; i < rocks.length; i++){
            if(rocks[i] - before < mid) {
                removeCnt++;
                continue;
            }
            before = rocks[i];
        }
        if(end - before < mid) removeCnt++;

        return removeCnt;
    }
    
}