Programmers, 징검다리

🔗 문제 링크 이분탐색 문제! 

 

문제 설명

출발지점부터 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 함수를 작성해주세요.

 

 

제한사항

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

 

입출력 예

distance	rocks	n	return
25	[2, 14, 11, 21, 17]	2	4

 

 

문제 해결

 

C++

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    int low=0, high=distance;
    vector<int> dist;
    
    sort(rocks.begin(), rocks.end());
    rocks.push_back(distance);
    
    while (low < high) {
        int mid = (low+high) / 2;
        int rm = 0, start = 0;
        
        for (int roc: rocks) {
            if (roc - start < mid) rm++;
            else start = roc;
        }
        
        if (rm <= n) {
            low = mid + 1;
            if (mid > answer) answer = mid;
        } else high = mid;
    }
    
    return answer;
}

 

문제 접근법

가장 먼저 이분탐색 조건으로 배열을 정렬한 후, [0 ~ 마지막 돌 ~ distance] 까지의 거리까지 고려하기 위해 distance를 배열에 추가합니다.

 

이분 탐색에서 먼저 짚고 가야할 것은 어떤 것을 검색할 것인지와 어떤 조건으로 필터링할 것인지를 정확히 해야하는 게 중요한 것 같아요. 

 

✔️ 어떤 것을 검색할 것인지 -> 돌 사이의 가능한 최소 거리 중 최댓값

✔️ 어떤 조건으로 필터링할 것인지 -> 최소한의 가능한 거리를 탐색 후 가능한 조건인지 판단 후 최댓값 반영

 

 

예제 입력값으로 설명을 이어가겠습니다.

 

// low = 0, high = 25, mid = 13
[0]  2  11  14  17  21  [25]

 

먼저 mid 값은 '최소 가능성이 있는 돌 사이의 거리'임을 확인하고!

이분탐색의 과정을 두 단계로 나누자면 아래와 같이 진행됩니다.

 

1. mid 값을 적용했을 때 결과값 도출  👉🏻 mid 거리를 최소로 설정했을 때, 바위가 몇 개 제거되는가

 

2. 결과값의 유효성 판단 후 범위 갱신  👉🏻  mid 거리를 최소로 설정했을 때, 제거된 바위가 n의 범위 내에 들어오는 유효값인가

 

위와 같이 두 단계로 나누었을 때를 함께 살펴보도록 할게요.

 

 

1. mid 값을 적용했을 때 결과값 도출

mid 거리를 최소로 설정했을 때, 바위가 몇 개 제거되는가

 

이 값이 최소값인지를 확인하는 과정으로 몇 개의 돌이 삭제되는 지를 체크해보면 아래와 같아요.

 

갱신되는 start 는  ↓ 로, 삭제되는 돌은 R로 표시하면 아래와 같습니다.

 

 ↓           ↓
[0]  2  11  14  17  21  [25]
     R   R       R   R    R

 

차근차근 보자면, 0에서 부터 시작해서 각각의 거리가 mid(13) 보다 작을 때 돌을 없애줄거예요.

0을 기준으로 첫 번째 바위의 위치 2는 mid 보다 작기 때문에 제거할 수 있습니다.

제거한다면, [0, 11, 14, 17, 21, 25] 의 형태로 보이겠죠. 

 

그럼 다음으로 두 번째 바위의 위치 11과의 거리를 볼까요? 마찬가지로 mid보다 작기 때문에 제거할 수 있습니다.

제거한다면, [0, 14, 17, 21, 25] 의 형태로 보이겠죠.

 

이 번에는 세 번째를 보도록 할게요. (참고로 삭제되는 돌의 개수는 지금 신경쓰지 않아요. 몇 개의 돌이 삭제되는지의 '가능성 판단'은 이분탐색의 범위를 지정할 때 판단합니다.) 이 번에는 mid 보다 크기 때문에 제거할 수 없어요.

그래서 제거하지 않고 네 번째로 넘어갑니다. 그럼 다음 바위와의 거리 비교는 이전의 돌인 [14] 로 설정을 해야할 테니, start를 갱신합니다.

 

 

이 과정을 모두 진행하게 되면, 제거되는 바위의 개수가 5개인 것을 확인하고, 이제 가능성 판단을 해야해요.

 

 

 

2. 결과값의 유효성 판단 후 범위 갱신

mid 거리를 최소로 설정했을 때, 제거된 바위가 n의 범위 내에 들어오는 유효값인가

 

mid가 13일 때 제거되는 바위는 5개입니다. n보다 큰 수입니다. 

그럼 어떻게 범위를 지정하면 될까요? 

바위를 줄여야겠죠? 그럼 high를 낮게 주면 되고, 이분탐색 알고리즘에 의해 high값을 mid 값으로 설정하면 됩니다.

 

 

이렇게 답을 찾을 때까지 진행하게 되는데요.

계속 진행시키면 아래와 같아요.

 

/* low = 0, high = 25, mid = 13
 * R = 5, 최소 거리 불가능
 */
 ↓           ↓
[0]  2  11  14  17  21  [25]
     R   R       R   R    R


/* low = 0, high = 13, mid = 6
 * R = 3, 최소 거리 불가능
 */ 
 ↓       ↓       ↓        ↓
[0]  2  11  14  17  21  [25]
     R       R       R    


/* low = 0, high = 6, mid = 3
 * R = 1, 최소 거리 가능.
 * 최소거리 중 최댓값을 찾기 위해 answer과 비교 후 계속 진행
 */
 ↓       ↓   ↓   ↓   ↓    ↓
[0]  2  11  14  17  21  [25]
     R 


/* low = 4, high = 6, mid = 5
 * R = 3, 최소 거리 불가능.
 */
 ↓       ↓       ↓        ↓
[0]  2  11  14  17  21  [25]
     R       R       R    


/* low = 4, high = 5, mid = 4
 * R = 2, 최소 거리 가능.
 * 최소거리 중 최댓값을 찾기 위해 answer과 비교 후 계속 진행
 */
 ↓       ↓       ↓   ↓    ↓
[0]  2  11  14  17  21  [25]
     R       R
     
     
// low = 5, high = 5 -> while 조건 탈출 ~

 

 

이해에 도움이 되셨나요 〰️ 

그럼 모두 즐코하세요.,,