[이분탐색] 징검다리 - JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

---

이 문제는 이해하는데 너무 오래걸렸다

시험에 나온다고 하면 풀이 방법도 감도 못잡고 끝났을 것 같다,,

후.. 진짜 백준으로 기강 다시 잡아야겠다..

 

암튼! 이 문제는 바위를 n개 제거한 후 각 지점 사이의 거리의 최솟값 중에서 가장 큰 값을 찾으면 된다

...?

탐색해야 할 값은 '지점과 지점 사이의 거리' 라는거! 이게 포인트다

 

 

문제 풀이 순서

1. rocks 배열 (바위 간 거리)을 정렬하고, 이분탐색을 위해 left=0, right=distance(목적지까지 거리)로 설정한다
2. mid = (left+right)/2 를 구한다. 이 떄 mid 값이 각 지점 사이의 거리의 최솟값이 되도록 만들어주는 것이다!
3. 이제 rocks 배열을 순회하면서 mid보다 작은 값이 있으면 해당 바위를 지운다
   • mid 값이 최솟값이 되어야 하니까 간격이 mid 보다 작은 경우 해당 바위가 존재하면 안된다
   • 따라서 해당 바위를 지워주는 것이다!
4. 만약 mid 보다 큰 값이 나타나면 그 바위는 존재해도 되므로 해당 바위로 건너뛴다
   • 여기서 건너뛴다는 것은 현재 위치를 그 바위로 옮긴다는 것이다
   • 따라서 prev라는 변수를 통해 해당 위치를 표현하고, mid보다 간격이 큰 바위가 있으면 해당 바위 위치로 prev를 변경해주는 것이다!
5. 위의 과정을 반복해주고, 최종 상태에서 총 지운 돌의 개수를 n과 비교한다
   • 만약 n개보다 돌을 더 많이 지웠으면, 돌의 개수를 줄여야 하므로 right 값을 mid-1 로 업데이트한다
   • 만약 n개보다 돌을 적게 지우거나 같게 지웠다면, answer에 mid값을 저장하고 left를 mid+1 로 업데이트한다
6. left 값이 right보다 커질때까지 위 과정을 반복하며 최적의 값을 찾는다

 

 

 

 

 

자바 코드)

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int left = 0;
        int right = distance;
        Arrays.sort(rocks);
        
        while(left<=right) {
            int mid = (left+right)/2;
            int removeRocks = 0;
            int prev = 0;
            
            for(int i=0;i<rocks.length;i++) {
                if(rocks[i]-prev < mid) {
                    removeRocks++;
                } else {
                    prev = rocks[i];
                }
            }
            if(distance-rocks[rocks.length-1] < mid) {
                removeRocks++;
            }
            if(removeRocks<=n) {
                answer = mid;
                left = mid+1;
            } else {
                right = mid-1;
            }
            
        }
        return answer;
    }
}

역시 이분탐색,, 쉽지않아,,,

 

---

참고)

https://born2bedeveloper.tistory.com/41

[프로그래머스] 징검다리-JAVA