[프로그래머스/JAVA] 고득점Kit > 이분탐색 > 징검다리 (by 다알쥐AI)

틱톡라이트 초대링크 https://lite.tiktok.com/t/ZSjqX7SfC/

[기간 한정] 보는 재미로, 버는 재미로! 영상만 봐도, 좋아요만 눌러도, 검색만 해도, 포인트가 차

[징검다리] 고득점Kit > 이분탐색 > 징검다리

 
 
※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※
[문제설명]

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.

예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

 위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

 

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

입출력 예

입출력 예 설명

문제에 나온 예와 같습니다.

---

[간단설명]
바위를 N개 제거 했을 때, 바위 사이 거리 최소값 중에서 최대값을 찾는 문제
 
[접근방법]
1. 시작지점, 종료지점을 포함하는 새로운 배열을 만든다.
2. 오름차순 정렬한다
3. mid 값을 정하고, 배열을 순회한다.
ㄴ> 이분탐색
4. 바위 사이 거리가 mid 값 보다 작으면 바위를 제거한다.
5. 바위를 제거하지 못했으면, 최소값을 저장한다
6. 바위 제거 개수가 N 이하이면,
    1) 최소값 중에 최대값을 찾는다.
    2) start를 mid값 +1 로 치환한다.
7. 바위 제거 개수가 N 초과이면,
    1) end값을 mid 값으로 치환한다.
8. max 값 리턴 
 
[주의사항]
1. 문제의 조건이 까다롭다. 
2. 이분 탐색의 조건을 잘 정하자.
ㄴ> 여기에서는 바위 사이의 적당한 거리를 구하는데 mid를 사용
3. rocks 배열의 길이가 n이면 distance 리턴(전부 제거되었을 때)
4. 바위 제거 시에, 바위 사이 거리는 바위 제거 전의 이전 위치와 현재 위치의 길이로 계산 해야한다.
5. min 값 역시 이전 위치를 가지고 계산 해야한다.
ㄴ> 바위가 1개 제거된 경우, 바위가 연속으로 제거된 경우 등 이전 위치가 중요
 
 
[소스공개]

import java.util.*;
class Solution {
    public int solution(int distance, int[] rocks, int n) {
        // 모든 바위를 제거 했을 경우, 전체길이 리턴 
        if (rocks.length == n) return distance;
        
        // 바위 정렬 
        Arrays.sort(rocks);
        int[] arr = new int[rocks.length+2];
        // 새로운 배열을 만든다 
        for(int i=1;i<arr.length-1;i++){
            arr[i]=rocks[i-1];
        }
        // 출발지점 넣어주기
        arr[0]=0;
        // 도착지점 넣어주기 
        arr[arr.length-1]=distance;
        
        // 바위 사이의 거리 시작점
        int start = 0; 
        // 바위 사이의 거리 종료점
        int end = distance;
        // 거리의 최소값들 중에 맥스값
        int max=-1;
        // 중간 지점을 찾을 때까지 반복 
        while(start<end){
            // 이분탐색
            // 범위를 반으로 줄여가면서,
            // 제거 해야할 바위의 적당한 거리를 찾는 과정
            // 적당한 거리란?? 바위 제거 개수가 N 에 근접했을 때의 mid 값
            // ex) start = 0, end = 25, mid = 12
            int mid = (start+end)/2;
            
            int remove=0;       // 바위 제거 개수
            int before=0;       // 이전 위치
            int min=distance;   // 거리 최솟값 
            // 배열 전체 순회 
            for(int i=1;i<arr.length;i++){
                // 현재 위치
                int now = arr[i];
                // 현재 위치 - 이전 위치 < mid 이면, 바위 제거
                if(now-before<mid){
                    remove++;
                }
                // 바위 제거를 못했으면, 거리 최소값 저장 
                else{ 
                    min=Math.min(min,now-before);
                    before=now; // 현재 위치를 기록, 다음 순회시 이전 위치 
                }
            }
            // 바위 제거 개수가 N 이하면, Max값 찾기, start 증가 
            // ex) start = 12 + 1 = 13
            if(remove<=n){
                max=Math.max(max,min);
                start=mid+1;
            // 바위 제거 개수가 N 초과면, end값 감소
            }else{
                end=mid;
            }
        }
        // max 리턴
        return max;
    }
}

 
[실행결과]