[BOJ 2110] 공유기 설치 (Python)

풀이

이 문제의 포인트는 이분 탐색을 활용해야 한다는 것이다. 이분 탐색은 오름차순으로 정렬된 N개의 데이터에서 원하는 값을 찾는(O(logN)) 알고리즘인데, 보통 이분 탐색에서 초기 left와 right값을 배열의 첫 인덱스와 마지막 인덱스로 설정한다. 하지만, 이 문제에서는 left와 right값을 좌표 거리값으로 설정하여 공유기를 설치할 거리 간격(mid)을 이분 탐색으로 갱신하면서 가장 인접한 두 공유기 사이의 거리의 최대값을 구하게 된다. 이러한 방식은 O(Nlogx)의 시간 복잡도로 줄여준다.

1. 집 좌표값을 오름차순으로 정렬한다. (이분 탐색을 하기 위함이다.)

2. left = 1로 right = 집 좌표의 최댓값(home[-1])으로 설정한다. 처음 공유기 설치할 거리 간격을 집 좌표값의 중간값으로 설정하여 탐색하기 위해서이다.

   • left = 집 좌표의 최솟값(home[0])으로 설정하면 안된다. (해당 부분때문에 오답이 많이 발생했다...)

     (반례) 5 3
     100
     101
     102
     103
     104
     --> left = 100(home[0])으로 설정하게 되면 공유기를 설치할 거리 간격이 100 아래로 절대 설정되지 않는다. 우리가 구하고자 하는 것은 '최대 간격'이다. 즉, 최대 간격은 home[0]보다 작을 수도 있기 때문이다.

3. 중간값(공유기 설치할 거리 간격)을 기준으로 집의 개수를 셌을 때 C보다 크면, left값을 증가시킨다. (left = mid + 1) --> 공유기 설치할 거리 간격을 늘려본다.

4. 중간값(공유기 설치할 거리 간격)을 기준으로 집의 개수를 셌을 때 C보다 작으면, right값을 감소시킨다. (right = mid - 1) --> 공유기 설치할 거리 간격을 줄여본다.

5. 위 과정을 left값과 right값이 같아질 때까지 계속 반복한다.

코드

import sys

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

# 이분 탐색을 위한 오름차순 정렬
home.sort()

# 거리의 최솟값은 시작점의 좌표가 아니다! left = home[0]으로 하면 안됨!
# 우리가 구하고자 하는 것은 '최대 간격'이다. 
# 최대 간격은 home[0]보다 작을 수도 있기 때문이다.
# 반례
# 5 3
# 100
# 101
# 102
# 103
# 104
left = 1
right = home[-1]
answer = 0
while left <= right:
    mid = (left + right) // 2   # 간격 설정
    curr_home = home[0]
    cnt = 1
    # 간격에 따른 공유기 설치
    for i in range(1, N):
        if home[i] - curr_home >= mid:
            cnt += 1
            curr_home = home[i]

    # 간격에 따라 공유기 설치했는데 이때 원래 설치하려던 공유기 개수와
    # 같거나 크면 간격을 증가시켜 공유기 다시 설치해본다.
    # --> 간격을 증가시켜 공유기 설치했을 때 두 공유기 사이의 최대 거리가 갱신될 수도 있기 때문에
    # 간격을 증가시킨채로 공유기를 설치해본다.
    if cnt >= C:
        answer = mid
        left = mid + 1

    # 간격을 감소시켜 공유기를 설치하여 C개 이상의 공유기를 설치하게 해본다.
    else:
        right = mid - 1

print(answer)