고정된 난방 반경을 가진 표준 히터를 설계해서 일직선상의 모든 집을 따뜻하게 해야 하는 상황을 가정해 봅시다. 집들의 위치와 히터들의 위치가 각각 주어졌을 때, 모든 집이 히터의 난방 범위 안에 들어오도록 만드는 히터의 최소 반경을 구하는 것이 이번 글에서 다룰 문제입니다.
예를 들어 입력이 [1,2,3,4], [1,4]라고 해 보겠습니다. 히터가 위치 1과 위치 4에 배치되어 있으므로, 반경 1만 확보하면 모든 집을 충분히 데울 수 있습니다. 따라서 기대 출력은 1입니다.
풀이 접근 방법
핵심 아이디어는 간단합니다. 각 집마다 가장 가까운 히터까지의 거리를 계산하고, 그 거리들 중 최댓값이 곧 필요한 최소 반경이 됩니다. 가장 가까운 히터를 빠르게 찾기 위해 정렬된 히터 배열에서 이진 탐색(bisect_left)을 활용합니다.
구체적인 단계는 다음과 같습니다.
houses 리스트를 오름차순으로 정렬합니다.
heaters 리스트를 오름차순으로 정렬합니다.
res := houses 배열과 같은 크기의 배열을 만들고 무한대(inf)로 초기화합니다.
i를 0부터 houses의 크기까지 반복합니다.
h := houses[i]
ind := h를 heaters에 삽입할 때 정렬 상태가 유지되는 가장 왼쪽 인덱스(bisect_left 결과)
ind가 heaters의 크기와 같다면(모든 히터가 집보다 왼쪽에 있는 경우), res[i] := min(res[i], |h − heaters[-1]|)
ind가 0이라면(모든 히터가 집보다 오른쪽에 있는 경우), res[i] := min(res[i], |h − heaters[0]|)
그 외의 경우에는 양옆의 두 히터 중 더 가까운 것을 선택합니다. 즉, res[i] := min(res[i], |h − heaters[ind]|, |h − heaters[ind−1]|)
모든 집이 커버되려면 가장 불리한 집 기준으로 계산해야 하므로, res의 최댓값을 반환합니다.
예제 코드
아래 파이썬 구현을 통해 동작 방식을 더 명확히 이해할 수 있습니다.
from bisect import bisect_left
class Solution:
def findRadius(self, houses, heaters):
houses.sort()
heaters.sort()
res = [float('inf')]*len(houses)
for i in range(len(houses)):
h = houses[i]
ind = bisect_left(heaters, h)
if ind==len(heaters):
res[i] = min(res[i], abs(h - heaters[-1]))
elif ind == 0:
res[i] = min(res[i], abs(h - heaters[0]))
else:
res[i] = min(res[i], abs(h - heaters[ind]), abs(h - heaters[ind-1]))
return max(res)
ob = Solution()
print(ob.findRadius([1,2,3,4],[1,4]))
입력
[1,2,3,4],[1,4]
출력
1
동작 원리와 복잡도
이 알고리즘은 각 집에 대해 이진 탐색 한 번으로 인접한 히터 후보를 찾아냅니다. 히터가 n개일 때 이진 탐색은 O(log n)이므로, 전체 시간 복잡도는 정렬 비용을 포함해 O((m + n) log n)(m은 집의 수, n은 히터의 수)입니다. 단순히 모든 집–히터 조합을 비교하는 O(m × n) 방식보다 훨씬 효율적이며, 입력 크기가 커져도 안정적으로 동작합니다.