링크
문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
풀이
-
두 공유기 사이의 거리를 구해야 한다. 거리는 변수이다. 공유기 수는 주어진 상수이다.
-
어쨌든 좌표는 주어져 있고 그 좌표에서 최대 거리는 있으니 단위 거리가 1이냐, 거리가 2이냐 에 따라 공유기를 몇 개나 놓을 수 있을지 달라진다.
-
예시를 보면 1,2,8,4,9가 주어졌고 일단 이거를 sorting해서 1,2,4,8,9로 만들면 최대 거리는 9-1 = 8이라는 걸 알 수 있다. 그러면 8 이내에서
-
단위 거리가 최소 1일 때 배치 할 수 있는 공유기의 수는?
-
단위 거리가 최소 2일때 배치할 수 있는 공유기의 수는?
-
...단위 거리가 8일때 배치할 수 있는 공유기의 수는?
라고 질문을 하며 필요한 공유기의 수를 찾을 수 있다.
-
-
근데 가장 먼 거리가 10억이라서 최대 거리가 9억 9000이 될 수도 있으니, 이위 거리를 하나씩 늘려가면서 보기에는 시간 복잡도가 꽤 커질 것 같다.
-
선형 탐색 쓰면 힘들 것 같고, 이진 탐색을 써서 탐색 범위를 강하게 좁혀야 한다.
-
일단 중앙값을 구해보자. 최소 단위 거리로 따졌을 때 최대 거리가 8이고, 최소가 1이니까 1+8 // 2 = 4로 나온다.
-
최소가 1인 이유 = 이 문제에서 집은 같은 좌표를 가지는 일이 없으니까 한 칸씩은 띄워져 있다. 그래서 최소가 1이다. 예시에서 1과 2의 간격이 1인데 그게 제일 작아서 최소가 1으로 나오는 건 아니다.
-
거리의 범위를 구하면 1 | 4 | 8 이렇게 시작, 중간, 끝이 나온다.
-
최소 단위 거리가 4일 때의 케이스 ⇒ 첫 좌표가 1이니까 그 다음 공유기는 5에 있을 수 있는데, 5는 좌표목록에서 없다. 그래서 그 다음 순위인 8에 공유기를 둬야 한다. (python의
bisect라는 built-in module 사용). ⇒ 공유기 수는 2개-
첫 좌표를 1로 고정시키고 풀어도 된다.
-
이유 : 예를 들어 출발점이 2이고, 같은 최소 간격을 유지한다고 했을 때, 출발점을 1로 바꿔도 최소 간격을 유지하는 게 깨지지 않는다. 즉, 간격이 동일하면 어떤 좌표에서 시작하든 크게 상관이 없다는 것.
-
더 자세한 이유는 아래 링크 참고!
-
-
최소 단위 거리가 4일 때 공유기 수가 2개이고, 우리가 구하는 공유기 수는 3개이니까 단위 거리를 줄여야 한다. 거리는 4보다 앞으로 가야 한다. end 포인터를 4-1인 3으로 둘 수 있다.
-
다시 중앙 값을 구하면 1+3 // 2 = 2가 나온다. 최소 단위 거리가 2일때의 케이스는 (1,4,8)이 나온다. (1,4,9)도 있지만 경우의 수를 구하는게 아니니까 어짜피 하나만 구하면 된다. 즉 공유기 수는 3개가 된다.
-
그러나 똑같이 공유기 수가 3개이지만 더 큰 거리가 있을 수 있으니, 더 진행해야 한다. 범위를 더 좁힌다. left(2) = median(2) + 1을 해서 범위를 3~3으로 좁힌다.
-
최소 단위 거리가 3인 케이스를 구해보면 (1,4,8)이 나온다. 범위는 3까지라 3이 답이 된다.
-
테스트 케이스
5 3
1
2
8
4
9
==
4 3
1
3
5
7
==
5 3
100
101
102
103
104코드(380ms)
import sys, bisect
op_lst = list(map(int, sys.stdin.readline().split())) # 집 개수, 공유기 개수 리스트
coord_lst = sorted([int(sys.stdin.readline()) for i in range(op_lst[0])]) # 좌표 리스트
start = 1 #최소 간격
end = max(coord_lst) - min(coord_lst) #최대 간격
while True:
median = (start+end)//2
# 단위 거리로 배치할 수 있는 공유기 수 구하기
starter = coord_lst[0]
starter_index = 0
router_count = 0
while starter_index<len(coord_lst):
router_count+=1
starter_index = bisect.bisect_left(coord_lst,coord_lst[starter_index]+median)
if router_count < op_lst[1]:
end = median - 1
elif router_count >= op_lst[1]:
start = median +1
if median == end: # 더 이상 큰 단위 거리를 구할 수 없을 때
print(median)
break