[프로그래머스 알고리즘 고득점 kit] 이분탐색 징검다리 - JAVA

🧐 문제

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치        각 바위 사이의 거리       거리의 최솟값
[21, 17]                         [2, 9, 3, 11]                   2
[2, 21]                           [11, 3, 3, 8]                   3
[2, 11]                           [14, 3, 4, 4]                   3
[11, 21]                         [2, 12, 3, 8]                   2
[2, 14]                           [11, 6, 4, 4]                   4

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.
출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

---

✅ 문제 이해

바위 21과 17을 제거했을 때 각 바위 사이의 거리는 [2,9,3,11]이며, 거리의 최솟값은 2라고 한다.

 

시작지점 ~ 도착지점까지 가면서 각 바위 사이의 거리를 측정하면 되므로, 위처럼 2, 9, 3, 12의 거리가 측정이 된다. 

이때, 거리의 최솟값은 2가 된다.

---

✅ 접근 방식

1️⃣ 완전 탐색 (🚫시간 초과)

가장 먼저 떠오르는 방식이라고 생각한다.

 

하지만 완전 탐색으로 접근할 때에는 시간 복잡도를 잘 계산해야 한다.

우선, 완전 탐색으로 접근하게 되었을 때는 조합을 이용하여 돌의 개수에서 제거해야 할 돌의 개수를 뽑아내야 한다.

 

바위의 개수를 k, 제거해야 할 바위의 개수를 n이라고 하면, 시간 복잡도는 다음과 같다.

 

그리고, 문제의 제한사항은 다음과 같다.

- 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
- 바위는 1개 이상 50,000개 이하가 있습니다.
- n 은 1 이상 바위의 개수 이하입니다.

최대 바위의 개수가 50,000개이므로 최악의 상황의 시간 복잡도는 n이 50,000k가 25,000일 때이다.

이때, 시간복잡도는 대략 10^15에 달한다..

 

무조건 시간 초과이니까 완전 탐색은 패스하자.

---

2️⃣ 이분 탐색

정렬이 된 상태에서 완전 탐색의 시간 복잡도를 획기적으로 줄일 수 있는 다음 방안책으로 이분 탐색을 떠올릴 수 있다.

 

그러나 이분 탐색으로 접근할 때는 다음과 같은 부분을 고려해야 한다.

 

☑️ left, right, mid 설정

어떤 변수를 이분탐색의 값으로 설정할 것인가? 는 중요한 문제이다.

 

이 문제에서 요구하는 return값은 바위 사이의 간격의 최솟값 중 최댓값을 구하는 문제이다.

따라서 바위 사이의 간격을 기준으로 문제를 풀어야 한다.

 

만약, distance가 25일 때, 바위가 전부 제거된 상태라고 가정해 보자.

이때 간격의 최솟값은 distance값인 25가 된다.

 

그러면 right값을 최댓값인 25로 설정하고 left값을 시작 지점인 0으로 설정하면서 이분탐색을 하면 어떨까에 대한 생각이 따라오게 된다.

💡left, right, mid는 평소 이분 탐색 문제를 풀 때처럼 index로 접근하는 것이 아닌, 간격을 기준으로, 값으로 접근하게 되는 것이다.

left : 시작 지점, 0
right : 도착 지점, distance
mid : (left + right) / 2

 

☑️ 이분탐색 조건문

앞서 봤던 완전 탐색은 돌멩이들을 하나씩 지워가며 거리를 측정하고 그 중 최솟값을 도출하는 것이 코드의 플로우였다.

<완전 탐색> -> 시간초과🚫
1. 돌멩이 두 개 제거
2. 거리 측정
3. 최솟값 도출

 

그러나 이분 탐색에서는 거리를 먼저 정하고(이분 탐색을 통해서) 거리에 맞게 돌멩이들을 지워나가며,

문제에서 요구하는 제거해야 할 돌멩이의 수와 비교하며 이분 탐색의 조건문을 수행하면 되는 것이다!

<이분 탐색>
1. 최솟값 거리(=mid) 설정 
2. 그거에 맞게 돌맹이 지워 나감 
3. 지워진 돌맹이 개수 확인 
4. 문제에서 요구하는 지워야 할 돌맹이 개수랑 똑같은가?

값을 기준으로 이분탐색을 진행한다고 앞서 언급하였다.

따라서 mid값이 거리의 최솟값이라 가정하며 조건문을 돌리며 mid값을 조정해 나갈 것이다.

 

그럼 이제 마지막 단계로 조건문은 어떤 기준으로 세울 것인가에 대한 문제를 고려해야 한다.

 

mid값은 최소거리라고 가정하였다.

그러면, 시작 지점부터 차례로 간격의 거리를 확인하면서 간격의 거리가 mid보다 작으면 최소거리라고 가정한 것이 모순되므로 간격에 해당하는 돌멩이들을 지워나가는 것이다.

 

🔎 이때, 지운 돌멩이들이 원래 지워야 할 돌멩이들보다 많이 지워버렸다면?

-> mid를 더 작게 해야 한다 -> 그래야 지워지는 돌멩이들이 적어지므로

 

🔎 반대로, 지운 돌멩이들이 지워야 할 돌멩이보다 적다면?

-> mid를 키워야 한다 -> 그래야 지워지는 돌멩이들이 많아지므로!!

 

그렇다면 조건문은 다음과 같아진다.

if (getCnt(rocks, distance, mid) <= n){
    answer = mid;
    left = mid + 1;
}else{
    right = mid - 1;
}

 

☑️ 전체적인 흐름 (그림)

그렇다면 이제 그림을 통해서 예제 문제를 가지고 전체적인 흐름을 파악하고자 한다.

 

(이분탐색에서 정렬은 필수다.)

▶️ 첫 번째 이분 탐색: left = 0, right = 25, mid = 12

[시작 ~ 첫 번째 돌멩이]

• 간격의 거리 : 2
• mid : 12

2 < 12 이므로 첫 번째 돌멩이는 지운다.

[시작 ~ 두 번째 돌멩이]

• 간격의 거리 : 11
• mid : 12

11 < 12 이므로 두 번째 돌멩이는 지운다.

[시작 ~ 세 번째 돌멩이]

• 간격의 거리 : 14
• mid : 12

14 > 12 이므로 세 번째 돌멩이는 지우지 않는다.

이때 그리고 시작 지점은 14로 다시 초기화한다.

[세 번째 돌이 ~ 네 번째 돌멩이]

• 간격의 거리 : 3
• mid : 12

3 < 12 이므로 네 번째 돌멩이는 지운다.

 

[네 번째 돌이 ~ 다섯 번째 돌멩이]

• 간격의 거리 : 7
• mid : 12

7 < 12 이므로 다섯 번째 돌멩이는 지운다.

 

이때, 지워진 돌멩이는 문제에서 요구하는 지워야 할 돌멩이보다 더 많다.
그러므로, mid 값을 더 작게 설정해야 한다.

right = mid - 1

 

▶️ 두 번째 이분 탐색: left = 0, right = 11, mid = 5

[시작 ~ 첫 번째 돌멩이]

• 간격의 거리 : 2
• mid : 5

2 < 5 이므로 첫 번째 돌멩이는 지운다.

[시작 ~ 두 번째 돌멩이]

• 간격의 거리 : 11
• mid : 5

11 > 5 이므로 두 번째 돌멩이는 지우지 않는다.

이때, 현재 위치를 11로 초기화해 준다.

[두 번째 돌멩이 ~ 세 번째 돌멩이]

• 간격의 거리 : 3
• mid : 5

3 < 5 이므로 세 번째 돌멩이는 지운다.

[두 번째 돌이 ~ 네 번째 돌멩이]

• 간격의 거리 : 6
• mid : 5

6 > 5 이므로 네 번째 돌멩이는 지우지 않는다.

이때, 현재 위치를 17로 초기화해 준다.

[네 번째 돌멩이 ~ 다섯 번째 돌멩이]

• 간격의 거리 : 4
• mid : 5

4 < 5 이므로 다섯 번째 돌멩이는 지운다.

 

이때, 지워진 돌이는 총 3개, 문제에서 요구하는 지워야 할 돌멩이(2개) 보다 더 많다.
그러므로, mid 값을 한번 더 작게 설정해야 한다.

right = mid - 1

 

 

▶️ 세 번째 이분 탐색: left = 0, right = 4, mid = 2

위와 같은 방식으로 진행하면 지워지는 돌멩이의 개수는 다음과 같다.

간격이 전부 2보다 크거나 같으므로, 지워진 돌멩이의 개수는 0개이다.

 

mid값을 크게 설정해야 한다.

left = mid + 1

 

 

▶️ 네 번째 이분 탐색: left = 3, right = 4, mid = 3

마찬가지로 위와 같은 방식으로 진행하면

위와 같은 결과가 나온다.

이때 지워지는 돌멩이는 첫 번째 돌멩이와 세 번째 돌이 총 2개이다.

 

하지만 아직 while문의 조건인 left <= right의 조건문을 탈출하지 못했으며,

해당 값이 문제의 요구사항은 만족하나 최댓값인지는 모르는 상태이다.

 

따라서 끝날 때까지 이분탐색을 진행해야 한다.

left = mid + 1

 

▶️ 다섯 번째 이분 탐색: left = 4, right = 4, mid = 4

이때도 지워지는 돌멩이의 개수는 첫 번째 돌멩이와 세 번째 돌이 총 2개이다.

 

mid값은 4이며, 전에 나왔던 3보다 큰 값을 가지고 있다.

문제에서 요구하는 부분은 최솟값 중 최댓값이므로 4가 답이 된다.

 

그리고 left를 한 번 더 조정함으로써 이분탐색 while문을 빠져나오게 된다.

---

✅ 코드 - JAVA

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        
        Arrays.sort(rocks); // 이분탐색 -> 정렬 필수
        
        int left = 0;
        int right = distance;
        
        while (left <= right){
            int mid = (left + right) / 2;
            if (getCnt(rocks, distance, mid) <= n){ // 만족하는 경우 answer = mid
                answer = mid;
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        
        return answer;
    }
    private int getCnt(int[] rocks, int distance, int mid){
        int before = 0;
        int remove = 0;
        int end = distance;
        
        for (int i = 0; i < rocks.length; i++){ // mid보다 작은 경우 돌멩이 제거
            if (rocks[i] - before < mid){
                remove ++;
                continue;
            }
            before = rocks[i];
            
        }
        if (end - before < mid){ // 마지막 돌멩이는 끝 지점과의 간격이므로 따로 카운트
            remove ++;
        }
        
        return remove;
    }
}