[이분탐색] 징검다리 - Java 코드 ★★★★

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

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

 

레벨 4지만 정말 어려웠다.

 

문제

 

이해

예제를 기준으로 다시 정리해보면

0 ~ 25 사이거리에 [2,11,14,17,21] 위치에 돌들이 존재하는 상황이며,

0 ~ 25 사이에서 어떤 위치값이 N개의 돌을 제거 했을때, 가질수 있는 최소 거리값들 중 최대값일까?이다.

 

예제와 같이 5개의 돌의 위치가 주어지면,

돌과 돌사이거리는 4개가 아니라,

시작위치 0 ~ 첫번째 돌사이, 마지막돌 ~ 끝지점 distance 사이 거리까지 포함해서

총 6개의 돌 사이 거리가 존재한다.   

 

풀이

N개의 돌을 제거하는 모든 경우를 만들어가면서 최솟값중에 최댓값을 구할 필요가 없다.

어떤 X 값 길이보다 돌과 돌사이의 거리가 작은 경우가 N개를 만족하도록 이분탐색을 해주면, 답이 구해진다. 

 

예제기준으로 설명하자면 0 ~ 25 사이에 범위에서 이분탐색을 하면서 

mid 값보다 작은 돌과 돌 사이거리의 갯수를 count해주어서 N를 만족하는지 체크해주면 된다.

import java.util.Arrays;
class Solution {
   public static int solution(int distance, int[] rocks, int n) {
      Arrays.sort(rocks);
      long answer=0;
      long start=0;
        long end=distance;
        while(start<=end) {
           long mid = (start+end)/2;
           long removeCnt=0;
           long prev=0;
           for(int i=0;i<rocks.length;i++) {// 모든 돌들의 사이값을 순회하면서 비교
              if(rocks[i] - prev < mid)    //사이값이 예상값보다 작은경우
                 removeCnt+=1;         // 돌을 제거가능하다고 판단
              else prev=rocks[i];
           }
           if(distance - prev < mid)   removeCnt+=1;   // 마지막돌과 끝거리사이도 제거가능한지 확인
           // removeCnt를 이용해 탐색값 ,범위 재설정
           if(n<removeCnt) 
              end = mid-1;              
           else {
              answer=Math.max(answer, mid);   //removeCnt==n이면 가능한 최소의 경우이므로 답으로 기록해야함
              start=mid+1;
           }
        }
        return (int)answer;
    }
}

코드상에서 임의에 해(mid값)보다 작은 돌 사이 거리는 제거 가능한 돌로 보고 Count해준다.

 

현재 mid 값에서 제거가능한 돌이 N보다 많다면, 그 보다 긴 돌이 많다는것 = mid값이 높은 상태이다.

      Right를  낮추어서 mid에 범위를 낮춰야 그보다 작은 사이 거리값의 갯수가 작아진다.

현재 mid 값에서 제거가능한 돌이 N보다 적다면, 그 보다 작은 돌이 거의없다는것 = mid값이 낮은 상태이다.

     Left를 높여서 탐색할 길이를 늘려주어야 제거 가능한 돌의 갯수가 많아진다.

 

( 위 내용이 혼돈이 될 수 있다. 천천히 읽어보며 상관관계를 이해하자) 

 

이분탐색에서 

Left 부분을 조정하는 구간에 = 을 넣어주면 Upper Bound (만족하는 최댓값) 을 구하는 풀이가 되고

Right 부분을 조정하는 구간에 = 을 넣어주면 Lower Bound (만족하는 최솟값) 을 구하는 풀이가 된다.

 

 

https://taesan94.tistory.com/154