[Lv4] 징검다리 - 이분탐색(BS)

출발지점부터 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

 

 

---

ㆍ제한사항의 1항에서 10억의 숫자를 보고 이진 탐색의 힌트를 얻는다.

ㆍ각 바위 사이의 거리를 벌리는 것이다. '거리'를 대상으로 푼다.

ㆍ주어지는 배열 rocks는 정렬된 상태가 아니다. 거리를 구하기 위해 먼저 rocks 배열을 정렬하고 시작한다.

 

 

최단 간격을 갖는 바위를 우선적으로 제거하고,

최단 간격 양 옆 중의 바위의 선택은, 바위가 없어져서 반대편 거리와 합쳐질 때 그 합쳐진 거리가 더 짧은 쪽을 선택하면 될 것 같지만...

아래의 예시를 보자.

(8) 돌 (8) 돌 (12) 돌 (13) 돌 (8) 돌 (8) 돌 (14) 돌 (19)

빨간 돌도 파란 돌도 양 옆의 간격이 8씩으로, 8도 같고, 8+8=16도 동일하다.

어느 돌을 선택하느냐에 따라 다음 번에 영향을 주고, 바위의 수는 최대 5만 개에 거리는 10억.

단순히 모든 경우의 수를 반복하기엔 메모리가 부족할 수도 있고 속도도 나오지 않는다.

 

 

이제 이분 탐색에서 뭘 기준으로 삼는가를 잘 캐치할 수 있어야 한다.

이건 많은 문제를 풀어보고 경험치를 높여야 한다는데...

여기서는 왼쪽에서 오른쪽으로 무작정(모든 간격의 최소치나 간격의 합 등을 고려하지 않고) '제거해나갈 수 있는 기준'으로 삼는다.

 

 

바위의 왼쪽 간격이 이 기준치 이하라면 제거한다.

(왼쪽 간격을 보면, 반복문에서 가장 마지막 간격은 검토 대상에서 제외된다. 이 간격은 바위 기준 오른쪽 distance와의 간격이라)

기준치를 초과한다면 제거하지 않고 다음 바위로 넘어간다.

모든 바위를 검토했을 때, 이 기준치에서 제거한 총 바위의 수를 센다.

바위를 n보다 더 많이 제거했다면 기준치가 높은 것이니 내려야한다(더 적게 부수도록. high = mid).

바위를 n보다 더 적게 제거했다면 기준치가 낮은 것이니 높여야한다(더 많이 부수도록. low = mid).

바위를 n만큼 딱 부수었어도 기준치는 높여본다. n보다 초과하지는 않지만 n만큼인 선에서 최대한 제거하도록 기준치를 높인다.

(우리가 이분 탐색하면서 찾는 것이 n이 아니며, 바위를 제거하는 기준임. 또한 최종 정답이 이 기준도 아닌 것도 기억)

 

 

이분 탐색시 맨 처음 low ~ high 값은 무엇이겠는가?

기준치로 간격을 판정한다고 했으니 이것도 간격이다.

모든 바위를 제거했다면 간격이 최대가 되고, 이 값은 distance와 일치한다.

즉, 0 ~ distance로 이분 탐색을 시작하면 된다.

 

 

이제 이분 탐색을 하면서 바위를 제거하는 횟수가 n이면서 바위를 부수는 기준이 한 곳으로 수렴할 수 있다.

근데 최종 제출 답이 이 기준이 아니라 n만큼 제거했을 때의 경우들 중에서

간격 중 가장 작은 값들을 대표로 했을 때에 그 중 최대인 값이다(얼마나 간격들을 고르게 넓게 퍼뜨렸냐는).

이분 탐색을 하면서 찾는 값과 최종 제출 값이 다르기 때문에, 이분 탐색을 하면서(기준을 구하면서) 마지막엔 간격 중 최솟값을 저장해둬야한다. 이 최솟값이 커져야하므로, 저장하는 값은 가장 큰 값 하나면 된다.

 

 

간격들은 최대 50002개가 될 수 있으니, 이 간격들을 훑는 때도 생각해보자.

만약 n이 3이라고 해보자.

이분 탐색에서 어떤 기준으로 바위들을 모두 제거했을 때, 제거한 수가 3보다 더 많을 때(4 이상인 때)의 간격들은 딱히 도움이 안된다.

n보다 더 많이 제거할 수 있다면 그냥 다 제거해서 최대 간격도 나올테니...

이분 탐색시 제거하는 수가 n과 같아질 때 간격의 최솟값을 구한다. 그리고 n보다 높아질 땐 더 이상 진행하지 않고 바로 기준치를 낮추는 다음 루프를 진행해도 된다.

n보다 더 적게 제거한 상황은 어떨까?(기준치가 낮아서 모든 간격을 훑었지만 n보다 적게 제거하고 끝난 상태)

이분 탐색으로 기준치를 시험해보는 과정에서 기준치가 낮다는 것을 안 것과 별개로

이 경우는 확실히 n보다 더 적게 제거하고도 간격을 많이 벌린 훌륭한 경우이다. 여기서 부족한 수 만큼 더 제거한다면 최소 간격은 더 벌어질 수 있다! 그러니 이 때의 간격 중 최솟값도 저장해야한다.

즉, 최솟값을 저장하는 때는 'n과 일치하게 제거했을 때'와 'n보다 적게 제거하고도 모든 간격을 훑게 되었을 때'이다.

 

 

기준치로 바위를 제거하는 과정도 보자.

물론 바위를 제거하면 바위 기준 왼쪽의 간격과 오른쪽의 간격이 합쳐지겠지만,

매 번 새로운 간격 배열을 재생성하는 것은 메모리 측면에서도 속도 측면에서도 비효율적이다.

(2)₀ (4)₁ (8)₂ (4)₃ (7)₄ (2)₅ (12)₆ (8)₇

인 배열을 보자(아래 첨자로 index 표기). 기준치가 7인 상황.

맨 처음에는 0번 index(값:2)를 오른쪽과 합칠지 말지 결정할 것이다(바위로 생각하면 0번과 1번 사이의 바위가 제거되어 양 간격이 합쳐지는 상황)

2는 7보다 작으니, 합쳐지면 된다.

(-)₀ (6)₁ (8)₂ (4)₃ (7)₄ (2)₅ (12)₆ (8)₇

합쳐진다면 index가 증가하고(이번엔 1번 index(값:6 =2+4)를 보게되니), 제거될 값이 다음 검토시에 합쳐지도록 기억만 하면 된다.

6(=2+4)도 7보다 작으니 합쳐질 것이다.

(-)₀ (-)₁ (14)₂ (4)₃ (7)₄ (2)₅ (12)₆ (8)₇

이번에도 index도 증가하고(이번엔 2번 index(값:14 =2+4+8)를 보게되니), 제거된 값도 합쳐졌다.(배열에 값을 변화시키면 다시 원복하거나 원본을 복제받거나 해야하니, 그냥 sum용 변수에 합치도록 한다)

14(=2+4+8)는 7보다 크니, 합쳐지지 않는다.

(-)₀ (-)₁ (14)₂ (4)₃ (7)₄ (2)₅ (12)₆ (8)₇

이번에는 index만 증가하고(이번엔 3번 index(값:4)를 보게되니), 검토하는 값은 3번 index의 값만 검토하면 된다.

 

바위를 제거할 때(간격이 합쳐질 때)는 index증가, 다음 번 검토시에 합친 값이 검토되도록 값을 저장.

바위를 제거하지 않을 때(넘길 때)는 index만 증가, 검토시에 같이 검토하던 값을 0으로.

(즉, index는 항상 증가. 검토시 같이 보는 값에 누적하거나 초기화하거나.)

 

 

이 간격을 훑는 과정에서 간격의 최솟값도 함께 구해야 시간복잡도를 늘리지 않을 수 있다.

(min은 이번 이분 탐색에서의 간격 중 최솟값. result는 전체 케이스에서 최솟값들 중 최댓값)

아직 바위를 제거한 수가 n을 넘기지 않은 때라면

바위를 제거하지 않을 때엔 넘어가면서 기존 값을 min과 비교하여 기록.

바위를 제거할 땐 계속 변할 값(더 누적될 수도 있는)이니 당장 신경쓰지 않아도 된다.

하지만 제거하는 수가 n이 된 순간에는 더 이상의 제거는 의미가 없으니,

n이 된 순간에 현재 검토하던 값과 그 뒤로의 간격들을 끝까지 모두 훑으면서 값들을 min과 비교하여 기록.

모두 훑은 후, 이 min이 result와 비교하여 그보다 크다면 기록 후 이분 탐색을 다시 하도록 한다.

n보다 적게 바위를 제거하고도 모든 간격을 훑은 경우라면, '마지막 간격'만 한 번 더 min을 검토하고

(바위 제거 반복문에서는 바위 기준 왼쪽 간격을 검토했기 때문에, 맨 마지막 바위의 오른쪽 간격에 해당하는 마지막 간격은 훑지 않았어서),

min이 result와 비교하여 그보다 크다면 기록 후 이분 탐색을 다시 하게 된다.

 

이렇게 이분 탐색에서 low ~ high가 한 곳으로 수렴한 상황에서

그동안 매 회 min들 중 최댓값을 기록한 result를 반환하면 된다.

 

그런데, 정말로 무작정 제거를 위한 기준을 찾는 이분 탐색 과정이

바위를 n개 제거하는 모든 경우를 훑어서 올바른 result를 기록하는 것이 맞냐는 물음에는 나도 확신이 안 선다.

이 포스팅은 나도 다른 사람들의 힌트와 전략을 내 방식대로 설명한 것에 그치지 않는다.

이 부분에 대해서는 알게되는 바가 있으면 더 기록하도록 하겠다.