알고리즘) 프로그래머스 BinarySearch, 징검다리

프로그래머스 고득점 Kit - Binary Search(이분 검색, 이진 검색)

징검다리

프로그래머스

풀이

 

이분 검색에서 mid값은 문제에서 요구하는 답으로 설정하는 것이 기본이다. 이 문제에서 원하는 답은 n개의 바위를 제거한 뒤 각 지점 사이의 거리의 최솟값이다. 따라서 left와 right, mid는 거리로 설정한다.

 

1. 돌위치를 돌면서 이전 돌과 거리를 비교한다.

2. 구한 거리가 가정 답안인 mid보다 작으면 최솟값이 mid가 될 수 없으므로 돌을 제거해준다. (counting을 해줌)

3. 거리가 크거나 같다면 돌은 그대로 놔두고, 이전 돌에 현재 돌의 값을 입력해준다.

4. for문을 돌고나서 마지막 돌과 도착지점의 거리도 구해줘서 count에 더해준다.

5. 제거한 돌의 수가 n이하면 거리의 최소 구간 left를 옮겨주고, return할 answer와 최대값을 비교하면서 대입해준다.

6. 5번이 아닌 경우 거리의 최대구간인 right를 옮겨준다.

 

코드

 

import java.util.Arrays;

public class KitBinarySearchSteppingStones {
    private static int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);
        return binarySearch(distance,rocks,n);
    }

    private static int binarySearch(int distance, int[] rocks, int n) {
        long answer =0;
        long left = 1;
        long right = distance;

        while(left < right) {
            long mid = (left+right) /2;     // 최솟값 x (가정 return 값)
            int prev =0;    // 이전 돌을 저장할 변수, 처음 시작은 주어진 시작점 0
            int cnt =0;     // 제거할 돌의 갯수를 count할 변수

            for(int i=0; i<rocks.length; i++) {
                if(rocks[i] - prev < mid) {     // 돌 사이의 거리가 최솟값인 mid보다 작으니까
                    cnt++;                      // 돌 제거
                } else {                        // 크거나 같은 돌이니까 남은 돌에 있을 녀석임
                    prev = rocks[i];            // 이전 돌을 현재 돌로 change
                }
            }

            // 도착점 distance 와 거리도 재야함
            if(distance- prev <mid) {           // 마지막 돌에서 distance까지가 mid보다 작으면 카운트
                cnt++;
            }

            if(cnt <=n) {   // 주어진 n 이하로 제거해서 최소값 만들 수 있음
                answer = answer > mid ? answer : mid;   // 최솟값 중 최댓값 입력
                left = mid+1;   // 최소 거리 범위 조정
            } else {        // 못만드는 경우
                right = mid;    // 최대 거리 범위 조정
            }
        }

        return (int)answer;
    }


    public static void main(String[] args) {
        int distance = 25;
        int[] rocks = {2, 14, 11, 21, 17};
        int n =2;

        System.out.println(solution(distance,rocks,n));
    }
}