도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi(0 ≤ xi≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제 입력 1
5 3
1
2
8
4
9
예제 출력 1
3
힌트
공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.
나의풀이
결론부터 말하면 시간 안에 못 풀었다.
집의 좌표 범위가 10억 단위라서 시간 복잡도를 맞추려면 parametric search를 해야 함은 알았지만 공유기 개수라는 제약 조건을 어떻게 만족시켜야할지 떠오르지 않았다.
참고한 풀이에선 parametric search를 통해서 얻은 공유기 사이 최대 거리를 기준으로 설치 가능한 공유기 개수를 설치해야 하는공유기 수와 비교했다.
import sys
# 공유기 설치 개수를 만족하면서 최대 거리를 찾는 것이 목적
def binary_search(house_pos : list, target_num : int):
# 최소 거리
start = 1
# 최대 거리
end = house_pos[-1] - house_pos[0]
# 공유기 설치 개수
while start <= end:
mid = (start + end) // 2
# 초기 위치는 고정
router_pos = house_pos[0]
# 공유기 개수 초기화
count = 1
for i in range(1, len(house_pos)):
if house_pos[i] >= router_pos + mid:
count += 1
# 위치 초기화
router_pos = house_pos[i]
# count가 target_num과 같을 때 최대 값을 구해야 하기 때문에 start를 올려 줌
if count >= target_num:
start = mid + 1
else:
end = mid - 1
print(end)
house_num, router_num = map(int, input().split())
house_pos = sorted([int(sys.stdin.readline().rstrip()) for _ in range(house_num)])
binary_search(house_pos, router_num)
참고한 풀이
'이것이 취업을 위한 코딩테스트다'에 있는 풀이를 참고했다.
이해하는 과정에서 주석을 조금 수정했다.
# 집의 개수(N)과 공유기의 개수(C)를 입력받기
n, c = map(int, input().split())
# 전체 집의 좌표 정보를 입력받기
array = []
for _ in range(n):
array.append(int(input()))
# 이진 탐색 위해 정렬 수행
array.sort()
start = array[1] - array[0] # 공유기 사이 거리 최솟값(첫번째 집엔 무조건 공유기를 설치하니까)
end = array[-1] - array[0] # 공유기 사이 거리 최댓값
result = 0
while start <= end:
mid = (start + end) // 2 # 가장 인접한 공유기 사이의 거리
value = array[0] # 공유기 초기 설치 위치
count = 1 # 공유기 설치 개수
# 현재의 mid(공유기 사이 거리)를 이용한 공유기 설치
for i in range(1, n): # 앞에서부터 설치
if array[i] >= value + mid:
# 공유기 설치 위치 변경
value = array[i]
# 개수 증가
count += 1
# c개 이상의 공유기를 설치할 수 있는 경우, 공유기 사이 거리 증가
if count >= c:
start = mid + 1
result = end
# c개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소
else:
end = mid - 1
print(result)
