99클럽 코테 스터디 22일차 TIL: [프로그래머스] 징검다리

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

프로그래머스

 

완전탐색으로 풀 경우, 50,000개의 바위 중 n개를 고르고(50,000 ^ n) 선택된 n개의 바위 간 간격을 구하므로(n) 약 50,000 ^ n * n의 시간복잡도를 갖는다. 따라서 시간 초과가 날 것이므로 다른 방법으로 풀어야 한다.

• 우선, 문제가 요구하는 것은 바위 간 간격의 최솟값 중 최댓값을 구하는 것이다.
• 이 문제는 이분 탐색으로 풀어야 하는데, 이분 탐색은 어떤 값을 left와 right로, 그리고 어떤 값을 mid로 지정하는지가 중요하다.
• left와 right는 mid가 될 수 있는 바위 범위이며, mid는 바위 간 간격의 최솟값이다.

예제를 통해 이해해보자. 다음 값이 주어졌을 때

 

이분 탐색을 위해 바위 위치들을 정렬한다. ➡️ 2, 11, 14, 17, 21

 

그리고 left = 0, right = 25, mid = 12((0 + 25) / 2)이다. 즉, 바위 간 간격의 최솟값이 12가 되어야 하며, 그렇게 되도록 2(n)개의 바위를 제거해야 한다.

• 우선 출발지점과 1번 바위 간 거리가 2이다. 바위 간 거리의 최솟값이 12가 되기 위해 1번 바위를 제거한다.
• 출발지점과 2번 바위 간 거리가 11이다. 마찬가지로 최솟값이 12가 되기 위해 2번 바위도 제거한다.
• 출발지점과 3번 바위 간 거리가 14이다. 따라서 3번 바위는 제거할 필요가 없다.
• 3번 바위와 4번 바위 간 거리가 3이다. 따라서 4번 바위를 제거해야 하는데, 이미 위에서 바위 2개를 제거했으므로 더이상 제거할 수 없다.
• 즉, 바위 간 거리의 최솟값이 12가 되도록 2개의 바위만 제거하는 것이 불가하다. 즉, 12는 바위 간 거리의 최솟값이 될 수 없다. 따라서 바위 간 거리의 최솟값이 12보다 더 작은 경우를 살펴봐야 한다.

따라서 right 값을 mid - 1로 줄여서 mid 값을 줄인다.즉, left = 0, right = 11, mid = 5인 경우를 살펴보자.

• 출발지점과 1번 바위 간 거리가 2이다. 따라서 1번 바위를 제거한다.
• 출발지점과 2번 바위 간 거리가 11이다. 
• 2번 바위와 3번 바위 간 거리가 3이다. 따라서 3번 바위를 제거한다.
• 2번 바위와 4번 바위 간 거리가 6이다.
• 4번 바위와 5번 바위 간 거리가 4이다. 따라서 5번 바위를 제거해야 하는데 이미 2개의 바위를 제거해서 더이상 제거할 수 없다.
• 즉, mid가 5인 경우 또한 불가능하다.

이어서 left = 0, right = 4, mid = 2인 경우를 살펴보자.

• 출발지점과 1번 바위 간 거리가 2이다. 
• 1번 바위와 2번 바위 간 거리가 9이다.
• 이어서 바위 간 거리가 3, 3, 4, 4이므로 mid인 2가 바위 간 거리의 최솟값이 된다.
• 따라서 answer = 2(mid)가 된다.

그런데 우리는 바위 간 거리의 최솟값의 최댓값을 구해야 한다. 따라서 left = mid + 1을 통해 mid 값을 늘려서 또 탐색해야 한다. 이어서 left = 3, right = 4, mid = 3인 경우를 살펴보자.

• 출발지점과 1번 바위 간 거리가 2이다. 따라서 1번 바위를 제거한다.
• 출발지점과 2번 바위 간 거리가 11이다.
• 2번 바위와 3번 바위 간 거리가 3이다.
• 이어서 바위 간 거리가 3, 4, 4이므로 mid인 3이 바위 간 거리의 최솟값이 된다.
• 따라서 answer = 3(mid)가 된다.

이어서 left = 4, right = 4, mid = 4인 경우를 살펴보자.

• 출발지점과 1번 바위 간 거리가 2이다. 따라서 1번 바위를 제거한다.
• 출발지점과 2번 바위 간 거리가 11이다.
• 2번 바위와 3번 바위 간 거리가 3이다. 따라서 3번 바위를 제거한다.
• 2번 바위와 3번 바위 간 거리가 6이다.
• 이어서 바위 간 거리가 4, 4이므로 mid인 4가 바위 간 거리의 최솟값이 된다.
• 따라서 answer = 4(mid)가 된다.

left와 right가 같은 지점까지 이분탐색을 진행했으므로, 가능한 모든 범위를 탐색했다. 그 중 mid의 최댓값이므로 답은 4가 된다.

 

이를 코드로 구현하면 다음과 같다.

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        
        Arrays.sort(rocks);
        int answer = 0;
        int left = 0;
        int right = distance;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            int cnt = 0; // 제거한 바위 개수
            int prev = 0; // 바위 간 거리 파악을 위한 시작 점
            
            for (int i = 0; i < rocks.length; i++) {
                // mid보다 바위 간 거리가 작으면 바위 제거
                if (rocks[i] - prev < mid) {
                    cnt++;
                    if (cnt > n) {
                        break;
                    }
                } else {
                    prev = rocks[i];
                }
            }
            
            if (distance - prev < mid) {
                cnt++;
            }
            
            // 현재 mid가 답이 될 수 없는 경우(-> mid 줄이기)
            if (cnt > n) {
                right = mid - 1;
            } 
            // 현재 mid가 답이 될 수 있는 경우(-> 최댓값을 구해야 하므로 mid 늘리기)
            else {
                answer = mid;
                left = mid + 1;
            }
        }
        
        return answer;
    }
}

 

이때 다음과 같이 마지막 바위부터 도착지점까지의 거리도 빠트리지 않아야 한다.

if (distance - prev < mid) {
    cnt++;
}