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

문제 링크

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

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

 

이 문제 역시 제한사항을 보면 1,000,000,000 이하 라는 어마어마한 범위를 가지고 있다.

즉, 완전탐색으로는 백퍼센트 타임오버라는 것이다.

따라서 효율적으로 값을 찾을 수 있는 이분 탐색을 사용할것이다.

 

 

 이분 탐색

 

https://born2bedeveloper.tistory.com/40

[프로그래머스] 입국심사-JAVA

해당 게시글의 이분 탐색 정리방법을 참고하자. 그림으로 쉽게 설명해놨다.

알고있다면 패스.

 

 

 풀이 과정

 

바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값

문제가 요구한 답이다. 

따라서 우리가 탐색할 값은 '지점과 지점 사이의 거리'이다.

그림과 함께 살펴보자.

 

1. 먼저 바위 사이의 거리를 담은 rocks[]를 오름차순으로 정렬한다.
   left = 0 , right = 25 (distance)로 설정한다.

2. mid를 구한다.

3. 출발지점 <-> 첫 번째 돌사이의 거리(2)가 mid(14)보다 작다.

해당 돌을 지워 간격을 더 길게 만들어준다.

4. 두 번째 돌과 prev(출발지점) 사이의 거리 (11)도 역시 mid(14)보다 작다.

해당 돌을 지워 간격을 더 길게 만들어준다.

5. 둘 사이의 거리가 (14)가 mid(14)와 같다. 
해당 돌을 지우지 말고 건너뛴다. prev를 해당 돌로 설정한다.

6. 이후에도 마찬가지로 mid보다 거리가 짧으면 해당 돌을 없에준다.

7. 일련의 과정을 마치면 징검다리의 상태가 이렇게 된다.

8. 징검다리의 돌을 지운 횟수 = 4개이다. 문제에서 제시한 지워야 할 돌의 개수 n과 비교한다.
n개보다 돌을 더 많이 지웠다면 right(도착지점)을 mid - 1로 설정한다.

n개보다 돌을 더 적게 지우거나 같게 지웠다면, answer = mid를 넣고 left를 mid + 1로 설정한다.

9. left > right가 될 때까지 1~8을 반복한다.

10. answer를 return한다.

 

 코드 풀이

 

import java.util.*;
class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int left = 0, 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;
    }
}

이분탐색 문제의 핵심은

1. left, right 범위 설정과 mid를 무엇으로 둘 것인지

2. mid를 left OR right로 옮길 조건을 설정하기

인 것 같다.

필자의 경우 돌을 하나씩 지워가며 거리를 맞춘다는 생각을 하기까지 참 오래걸렸다.

멀고도 험한 알고리즘의 길.. 언제쯤 번뜩이며 바로바로 문제를 해결할 수 있을까