공유기 설치

풀이

  이 문제는 가장 인접한 두 공유기 사이의 거리의 최댓값을 탐색해야 하는 문제다. 이때 각 집의 좌표가 최대 10억이므로 이진 탐색을 이용하면 문제를 해결할 수 있다. 매 순간 실제로 공유기를 설치하여 목표인 C와 값을 비교하여 범위를 조절해가면서 최적의 해를 구하면 된다. 시간복잡도는 리스트 정렬이 NlogN, 이진 탐색이 NlogM(M = 최대값 - 최소값)이다. 문제에서 N의 범위(2<=N<=200000)보다 M의 범위(1<=M<=10000000000)가 더 크므로 전체 시간복잡도는 NlogM이다.

import sys
N, C = map(int, input().split())
data = []
for _ in range(N):
    data.append(int(sys.stdin.readline()))
data.sort()

result = []
def binary_search(start, end):
    if start > end:
        return
    target = (start + end)//2
    count = 1
    x = data[0]
    for i in range(1, len(data)):
        if x + target <= data[i]:
            x = data[i]
            count += 1
    if count < C:
        binary_search(start, target-1)
    else:
        result.append(target)
        binary_search(target+1, end)

binary_search(1, data[-1] - data[0])
print(result[-1])

시간복잡도 : O(NlogM) (M : data 리스트의 최대값 - 최소값)