문제 이해하기
여러 개의 버킷과 x개의 공이 주어진 상황을 가정해 보겠습니다. 공을 버킷에 넣으면 공들 사이에 특수한 힘이 작용하는데, 우리는 이 힘의 최솟값을 최대화하는 방법을 찾아야 합니다. 위치 p와 q에 있는 두 공 사이의 힘은 |p − q|로 정의됩니다.
입력으로는 버킷들의 위치를 담고 있는 배열과 공의 개수 x가 주어지며, 가능한 모든 배치 중에서 두 공 사이의 최소 힘이 가장 커지도록 공을 배치해야 합니다.
예시
입력이 다음과 같다고 해봅시다.
pos = [2, 4, 6, 8, 10, 12], x = 3
이 경우 출력은 4입니다.
12개의 버킷 배열 안에서 공들은 주어진 위치에 배치될 수 있습니다. 세 개의 공을 각각 위치 4, 8, 12에 놓으면 인접한 공들 사이의 힘은 4가 되며, 어떤 배치로도 이 값을 더 크게 만들 수 없습니다.
접근 방법: 이진 탐색
이 문제는 이진 탐색(Binary Search)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "최소 거리 d가 주어졌을 때 x개의 공을 배치할 수 있는가?"라는 질문의 답이 d에 대해 단조적(monotonic)이라는 점입니다. 즉, d가 작을수록 배치가 쉬워지고, 클수록 어려워집니다. 따라서 가능한 d 값의 범위를 이진 탐색으로 좁혀 가며 최적의 값을 찾을 수 있습니다.
알고리즘 단계
- ball_count(d) 함수 정의: 최소 거리 d를 유지하면서 배치할 수 있는 공의 최대 개수를 계산합니다.
- ans := 1 (첫 번째 공은 항상 첫 위치에 배치)
- curr := pos[0]
- i를 1부터 n−1까지 순회하며, pos[i] − curr ≥ d이면 ans를 1 증가시키고 curr := pos[i]로 갱신
- ans 반환
- n := pos의 크기를 구하고, pos 배열을 오름차순으로 정렬합니다.
- 탐색 범위를 설정합니다: left := 0, right := pos[-1] − pos[0]
- left < right인 동안 반복합니다.
- mid := right − (right − left) // 2
- ball_count(mid) ≥ x이면 left := mid (거리를 더 늘려볼 수 있음)
- 그렇지 않으면 right := mid − 1 (거리를 줄여야 함)
- left를 반환합니다. 이 값이 최대화된 최소 힘입니다.
구현 예제
다음 코드를 통해 실제 구현을 확인해 보겠습니다.
def solve(pos, x):
n = len(pos)
pos.sort()
def ball_count(d):
ans, curr = 1, pos[0]
for i in range(1, n):
if pos[i] - curr >= d:
ans += 1
curr = pos[i]
return ans
left, right = 0, pos[-1] - pos[0]
while left < right:
mid = right - (right - left) // 2
if ball_count(mid) >= x:
left = mid
else:
right = mid - 1
return left
print(solve([2, 4, 6, 8, 10, 12], 3))입력
[2, 4, 6, 8, 10, 12], 3
출력
4
동작 원리 살펴보기
예제에서 전체 범위는 2부터 12까지이므로 초기 탐색 범위는 [0, 10]입니다. 이진 탐색은 매번 후보 거리(mid)를 정한 뒤, 해당 거리 이상을 유지하면서 3개의 공을 배치할 수 있는지 확인합니다. 배치가 가능하면 거리를 늘려 시도하고, 불가능하면 거리를 줄입니다. 그 결과 최소 힘이 4일 때 공을 위치 4, 8, 12에 배치할 수 있다는 것을 알 수 있으며, 이것이 바로 정답입니다.
시간 복잡도
정렬에 O(n log n)이 필요하고, 이진 탐색의 각 단계마다 O(n) 검사가 수행되며 탐색 자체는 최대 거리 D에 대해 O(log D)번 반복됩니다. 따라서 전체 시간 복잡도는 O(n log n + n log D)로, 모든 경우를 완전 탐색하는 방법보다 훨씬 효율적입니다.