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

일전에 작성했던 parametric search를 이용한 휴게소 세우기 문제와 유사한 문제이다. (해당 문제보다 살짝 더 쉬움)
👉🏻 백준 1477 휴게소 세우기 포스팅
👉🏻 프로그래머스 43236 문제 링크

문제
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

문제에서 나와있듯이 '바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값'을 구하면 되는 문제이다. 구간의 최솟값 중 가장 큰 값을 찾으면 된다.

문제 해결 아이디어

1. 지점 사이의 거리의 최솟값 중에 가장 큰 값
   이 조건을 통해 지점 사이의 거리를 중심으로 코드를 전개해야 된다는 것을 알 수 있다.
2. 최솟값 중에 가장 큰 값
   최솟값 중에 가장 큰 값을 구하는 부분은 이분탐색을 통해 구간을 설정하며 구할 수 있다는 걸 깨달아야 한다.

1, 2 조건을 통하여 이분 탐색을 이용해서 바위를 중점으로 생각하는 게 아닌, 구간을 중점으로 코드를 작성해야 한다는 것을 알았다.

이럼 90% 정도는 성공했다!

이분 탐색 중점 풀이

*먼저, 현재 rocks.length에서 n값을 뺀 것이 최종 돌의 개수이고 돌에 개수에 의해 구간은 최종 돌의 개수 +1개가 된다. (돌이 3개인 경우 구간은 4개가 됨)

간격은, 1<=간격<=distance이다.
간격이 0인 경우는 없고 만약 돌이 하나도 없다면 간격은 distance 만큼이기 때문!
그래서 left=1, right=distance로 설정하고 이분탐색을 수행한다.

left, right의 중간값인 mid로 현재 간격을 구한 후,

1. 해당 mid로 distance를 나눴을 때 몫이 정답 구간 개수보다 작은 경우
   -> 현재 mid가 너무 크다는 뜻이기 때문에 이분탐색에서 현재 구간을 줄인다.
   -> right=mid-1을 하여 mid 이상은 이제부터 고려하지 않기로 한다. ( Parametric search)

2. 해당 mid로 distance를 나눴을 때 몫이 정답 구간 개수보다 같거나 많은 경우
   -> 현재 mid(구간의 최솟값)으로 나눴을 때 정답 구간 개수보다 같거나 많으면 최솟값이 될 확률이 있다는 뜻이다. 이는 모든 구간이 동일하게 mid값이 아니기 때문에 많은 경우 또한 고려해야 한다.
   -> 현재 rocks 배열을 이용하여 최솟값을 만족하면 section으로 간주하고 count, 만족하지 않으면 다음 돌까지의 거리를 집계하여 최솟값 여부를 파악하는 메소드를 통해 검증한다.

    private boolean isPossible(int distance, int section, int[] rocks, int ansSection){
        int min=0;
        int sectionCnt=0;
        
        for(int rock:rocks){
            int dist=rock-min;
            
            if((dist/section)<1)
                continue;
            
            sectionCnt++;
            min=rock;
        }
        
        int lastDist=distance-min;
        if((lastDist/section)>=1)
            sectionCnt++;
            
        
        if(sectionCnt>=ansSection)
            return true;
        
        return false;
    }

해당 메소드에서 sectionCnt(구간 카운트)가 정답 구간 갯수보다 크거나 같은 경우 최솟값을 만족한다. 큰 경우에도 만족하는 이유는 현재 최솟값에 맞추어 구간을 구한 값이기 때문에 최솟값은 유지하고 구간을 병합하여 구간을 줄일 수 있기 때문이다. 어차피 이 값 이후에 구간을 높여서 다시 구간 값을 계산하고 더 큰 구간으로 구간 카운트를 계산하기 때문에 최솟값의 최댓값은 갱신되어 큰 상관이 없다.

💻 코드 첨부 💻

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        
        Arrays.sort(rocks);
        int ansSection=rocks.length-n+1;
        
        //Parametric search
        int left=1; int right=distance;
        int ans=distance;
        while(left<=right){
            int mid=(left+right)/2;
            
            if((distance/mid)<ansSection){
                right=mid-1;
                continue;
            }
            
            if(isPossible(distance, mid, rocks, ansSection)){
                left=mid+1;
                ans=mid;
            } else{
                right=mid-1;
            }
        }
        
        return ans;
    }
    
    private boolean isPossible(int distance, int section, int[] rocks, int ansSection){
        int min=0;
        int sectionCnt=0;
        
        for(int rock:rocks){
            int dist=rock-min;
            
            if((dist/section)<1)
                continue;
            
            sectionCnt++;
            min=rock;
        }
        
        int lastDist=distance-min;
        if((lastDist/section)>=1)
            sectionCnt++;
            
        
        if(sectionCnt>=ansSection)
            return true;
        
        return false;
    }
    
}

코드는 바로 작성했는데 블로그에 글로 옮겨쓰니 설명하기가 상당히 어렵다 😅