공유기 설치

입력조건

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력 조건

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

풀이 방식

이 집의 좌표가 최대 10억까지이다. 그래서 이진탐색을 통해서 '가장 인접한 두 공유기 사이의 거리'를 조절해가며, 매 순간 실제로 공유기를 설치하여 C보다 많은 개수로 공유기를 설치할 수 있는지 체크하며 문제를 풀 수 있다. 여기서 '가장 인접한 두 공유기 사이의 거리'의 최대값을 찾아야 하므로, C보다 많은 개수로 공유기를 설치할 수 있다면 start값을 증가시키면서, 더 큰 값도 가능한지 체크를 해야한다. 물론 반대인 경우는 end값을 감소시키면서 찾아야 한다.
그래서 아래와 같은 소스코드가 나왔다.

코드

import sys

N, C = map(int, sys.stdin.readline().split())
array = []
for _ in range(N):
    array.append(int(sys.stdin.readline().strip()))

array.sort()

start = 1  # 최소 거리
end = array[-1] - array[0]  # 최대 거리
result = 0  # mid값 저장하는 변수


if C == 2:  # 공유기 2대 설치 가능하면 처음과 끝 원소 차이 result에 저장
    result = array[-1] - array[0]

else:
    while start <= end:  # 이분탐색 시작
        mid = (start + end) // 2  # 간격 계산
        value = array[0]  # 맨 처음 원소에 공유기 설치
        count = 1  # 공유기 설치 가능한 위치 개수
        for i in range(1, N):  # 처음부터 끝까지 분석
            if array[i] >= value + mid:  # 공유기를 설치할 수 있는 간격인지 체크
                value = array[i]  # 공유기 설치 위치 변경
                count += 1  # 공유기 설치 가능한 위치 개수 추가

        if count >= C:  # 공유기를 C와 같거나 더 크게 설치할 수 있는 경우
            result = mid  # 우선 result에 저장
            start = mid + 1  # start를 mid + 1로 변경해서 더 높은 수의 간격이 가능한지 체크
        else:  # 공유기를 C보다 설치를 못하는 경우
            end = mid - 1  # end를 mid - 1로 변경해서 더 낮은 수의 간격이 가능한지 체크

print(result)