[백준] 2110번: 공유기 설치 - [Python/파이썬]

문제

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

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

출력

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

코드

import sys
input=sys.stdin.readline

data=[]
n, c =map(int, input().split())
for i in range(n):
    data.append(int(input()))

data.sort()
start, end=1, data[-1]-data[0]
answer=0

while start<=end:
    mid=(start+end)//2
    router=data[0]
    count=1

    for i in range(1, len(data)):
        if data[i]>= router+mid:
            count+=1
            router=data[i]
    if count >=c:
        start = mid +1
        answer = mid
    else:
        end=mid-1

print(answer)

문제 해결

이분 탐색을 활용한 코드이고 생각보다 코드를 작성하기 어려웠다

문제의 접근 순서는 다음과 같다.

1. 주어진 집들의 좌표를 오름차순으로 정렬한다 (이분 탐색의 기본 조건).
2. 집들 사이의 거리를 초기화한다. 최솟값은 1이며, 최댓값은 끝집과 첫집 사이의 거리이다.
3. 집들 사이의 거리를 기준으로 이분 탐색을 진행한다. 주어진 간격 (mid)으로 공유기를 설치했을 때, 주어진 조건을 충족하는지 확인한다.
4. 3번을 만족하는 거리들 중 최댓값을 출력한다.