알고리즘
이진 탐색
시간 복잡도
O(n + log n) => O(log n)
문제 풀이
N, M = list(map(int, input().split()))
houses = [int(input()) for _ in range(N)]
# 1. 집의 위치 정렬
houses.sort()
# 2. 공유기를 설치할 수 있는지 확인하는 함수
def can_install(min_dist):
count = 1 # 첫 집에 설치됨
last_pos = houses[0] # 이전 위치
# 이미 1은 설치되어 있다고 설정
for i in range(1, N):
# 현재 위치 - 이전 위치가 min_dist 보다 크거나 같은가?
if houses[i] - last_pos >= min_dist:
count += 1
# 이전 위치 현재 위치로 업데이트
last_pos = houses[i]
return count >= M
# 3. 이분 탐색
# 제일 낮은 위치
low = 1
# 가장 높은 위치
high = houses[-1] - houses[0]
result = 0
while low <= high:
mid = (low + high) // 2
if can_install(mid):
result = mid
low = mid + 1 # 더 큰 거리 도전
else:
high = mid - 1 # 거리 줄이기
# 출력: 가장 인접한 두 공유기 사이의 최대 거리
print(result)처음에는 문제를 잘 이해하지 못했고 접근도 쉽게하지 못했다.
팀원들과 계속 상의하면서 의견을 공유하고, 접근 방법에 대해 찾아갔지만
코드로 어떻게 구현해야 할지 쉽게 생각이 떠오르지 않았다.
다른 팀원 친구의 도움을 받아 
실마리를 찾게 되었다.
mid값의 변화를 주면서 min_distance를 찾는다.
mid값의 변화는 low 혹은 high 값을 변경하면서 줄여가거나, 늘려가는 방식으로 최소 간격을 찾는 이진 탐색이다.
developer