1차원 직선 위에 집들의 위치를 나타내는 숫자 리스트 nums가 주어졌다고 가정해 보겠습니다. 우리는 이 직선의 어느 위치에든 배치할 수 있는 가로등 3개를 가지고 있으며, 위치 x에 놓인 가로등은 반경 r을 기준으로 [x − r, x + r] 범위(양 끝 포함)에 있는 모든 집을 밝힙니다. 이때 모든 집을 밝히기 위해 필요한 최소 반경 r을 구하는 것이 이 문제의 목표입니다.
예를 들어 nums = [4, 5, 6, 7]이 입력으로 주어지면 결과는 0.5입니다. 가로등을 각각 4.5, 5.5, 6.5 위치에 놓으면 r = 0.5만으로 네 집 전체를 밝힐 수 있기 때문입니다.
문제 해결 접근 방법
이 문제는 그리디 방식의 유효성 검사(valid)와 이진 탐색(binary search)을 결합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
주어진 반경 r로 가로등 3개가 모든 집을 커버할 수 있는지 판단하는 valid(r) 함수를 정의합니다.
첫 번째 집을 기준으로 첫 가로등을 nums[0] + r 위치에 배치하고, 사용한 가로등 수 count를 1로 초기화합니다.
집들을 순서대로 확인하면서, 현재 마지막 가로등의 커버 범위를 벗어난 집이 등장하면 새로운 가로등을 해당 집 오른쪽 경계(val + r)에 배치하고 count를 증가시킵니다.
순회가 끝난 뒤 count가 3 이하이면 true, 아니면 false를 반환합니다.
메인 로직에서는 리스트를 먼저 정렬한 뒤, left = 0, right = 마지막 집의 좌표로 설정하고 이진 탐색을 진행합니다.
mid 값이 유효하면 res를 갱신하고 탐색 범위를 줄이고(right = mid), 유효하지 않으면 left를 mid로 옮깁니다. 부동소수점 정밀도를 확보하기 위해 반복을 충분히(예: 20회) 수행합니다.
구현 예시
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, nums):
def valid(r):
last_location = nums[0] + r
count = 1
for i in range(len(nums)):
val = nums[i]
if val - last_location > r:
count += 1
last_location = val + r
return count <= 3
nums.sort()
left = 0
right = nums[-1]
res = float("inf")
itr = 0
while left <= right and itr < 20:
mid = left + (right - left) / 2
if valid(mid):
res = min(res, mid)
right = mid
else:
left = mid
itr += 1
return res
ob = Solution()
nums = [4,5,6,7]
print(ob.solve(nums))
입력
[4,5,6,7]
출력
0.5
복잡도 분석
valid(r) 검사에는 O(n)의 시간이 걸리고, 이진 탐색을 고정 횟수(20회)만큼 반복하므로 전체 시간 복잡도는 O(n log m)(m은 좌표 범위 크기)이 됩니다. 정렬에 O(n log n)이 추가되므로 실질적인 총 복잡도는 O(n log n) 수준으로, 집의 수가 많아져도 효율적으로 동작합니다.