[Binary Search] 이코테 “공유기 설치” Python 풀이

문제

• 도현이의 집 N개가 수직선 위에 있다.
• 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
• 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다.
• 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고,
• 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
• C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력 조건

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

출력 조건

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

입력 예시

5 3
1
2
8
4
9

출력 예시

3

풀이

• 중요한 부분

  • 문제가 원하는 것은, 가장 인접한 두 공유기 사이의 거리가 최대인 것이지만,
  • 결국, 모든 공유기들의 간격이 공평하게 설치되기를 원한다고 해석할 수 있습니다.
  • 따라서, 모든 공유기들을 공평하게 설치할 수 있는 간격을 이분 탐색을 통해 찾아야합니다.

• 진행 순서

  1. 공유기 설치 좌표들을 오름차순으로 정렬합니다.
  2. 공유기를 설치할 수 있는 최소 간격과 최대 간격을 구한 뒤, 공유기를 가장 공평하게 설치할 수 있는 간격(mid)을 구합니다.
  3. 첫 번째 집에 공유기를 설치한 뒤, 첫 번째 집에서 나머지 집들 간의 간격을 확인하며, mid 이상으로 떨어져 있는 집을 탐색합니다.
  4. 첫 번째 집으로부터 mid 이상 떨어진 집을 찾은 경우, 해당 집에 공유기를 설치한 뒤, 해당 집 기준으로 다시 mid 만큼 떨어져있는 집을 탐색합니다.
  5. 모든 집을 탐색했다면, 공유기 설치 간격을 이분법을 사용해 갱신합니다.
     1. 현재까지 설치한 공유기의 개수가 아직 C개 이하라면, 기존 간격이 너무 크다는 의미이므로, 기존 간격보다 더 작은 간격으로 갱신합니다.
     2. 현재까지 설치한 공유기의 개수가 C개 이상이라면, 기존 간격이 너무 작다는 의미이므로, 기존 간격보다 더 큰 간격으로 갱신합니다.
  6. 가능한 모든 간격들을 탐색할 때까지 이분법 과정을 3번~5번 반복합니다.
  7. 탐색된 최대 간격을 반환합니다.

• 그림으로 이해

  

예제 코드

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

import sys

# 집의 개수(N)와 공유기의 개수(C)를 입력 받기
n, c = map(int, sys.stdin.readline().split())

# 전체 집의 좌표 정보를 입력 받기
array = []
for _ in range(n):
    array.append(int(sys.stdin.readline()))
# 이진 탐색 수행을 위해 정렬 수행
array.sort()

# 공유기를 설치할 수 있는 최소 간격
start = 1
# 공유기를 설치할 수 있는 최대 간격
end = array[-1] - array[0]
# 최종 공유기 설치 간격
result = 0

def bs(array, start, end):

    global result

    if (start > end):
        return result

    # 가장 처음으로 공유기를 설치하는 집의 위치
    recent_dist = array[0]
    # 공유기 설치 개수
    count = 1
    # 공유기 설치 간격
    mid = (start + end) // 2

    # 현재의 mid 값을 이용해 공유기를 설치
    for i in range(1, n):
        # 가장 최근에 공유기를 설치한 집과 mid 간격 이상으로 떨어졌다면, 공유기 설치
        if (array[i] - recent_dist >= mid):
            recent_dist = array[i]
            count += 1

    # 설치된 공유기의 개수가 c개 이상이라면, 해당 간격을 저장하고, 간격을 더 늘리기
    if (count >= c):
        result = mid # 최적의 결과를 저장
        return bs(array, mid+1, end)

    # 설치된 공유기의 개수가 c개 미만이라면, 간격을 더 줄이기
    else:
        return bs(array, start, mid-1)

print(bs(array, start, end))

참고

• 이것이 취업을 위한 코딩 테스트다. with python