백준 - 2110번 공유기 설치(이분탐색)

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

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

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

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

접근 방법
둘째 줄에 주어지는 집의 좌표가 최대 10억까지 이므로 2초내에 풀기 위해선 집의 좌표를 숫자로 생각하여 풀어야 하고.
제한된 공유기 수 안에서 거리를 최대한 벌려서 설치 하는 것을 목적으로 한다.
집의 개수가 N이라고 한다면 각 집 간의 거리의 개수는 N-1개,
N-1개의 거리를 내림차순으로 정렬하여 공유기 개수에 할당한 뒤 마지막 할당 값으로 하면 안되나?

a=[*open(0)]
N,C=map(int,a[0].split())
l=sorted(list(map(int,a[1:])))

# 거리를 기준으로 이분탐색하는 로직
# s는 최소거리
# m는 최대거리
def bs(s,m,li,c):
    while(s<=m):
        mid = (s+m)//2
        cnt=1
        pre = li[0]
        # 첫 공유기 위치=첫 집의 위치에서 
        #다음 집까지 거리를 재보면서 
        #최초 설정한 mid 보다 크거나 같으면 공유기를 설치하는 로직
        for l in li[1:]:
            if (l-pre) >= mid:
                cnt+=1 # 공유기를 추가 설치
                pre=l  # 
                
        # 루프를 다 돌았는데 mid가 너무 커서 공유기를 다 설치하지 못한 경우 최대 공유기 거리를 현재 공유기 거리보다 1 줄임
        if cnt < c: m=mid-1
        
        # 공유기가 초과 설치 된 경우 최소 공유기 거리를 현재 공유기 거리보다 1 늘림
        else: s=mid+1
    return m # mid를 리턴하는 것이 아닌 최대 공유기 거리인 m을 리턴해야 됨!
print(bs(1,l[-1]-l[0],l,C))
        

숏코딩 분석하기

n,c,*x=map(int,open(0).read().split())
x.sort()
l,h=1,x[-1]-x[0]
while l<=h:
 m=(l+h)//2;b=1;p=x[0]
 for q in x:
  if q-p>=m:b+=1;p=q
 if b<c:h=m-1
 else:l=m+1
print(h)

read() f.read()는 파일의 내용 전체를 문자열로 리턴한다.
그러므로 open(0).read().split()을 하게 되면
입력이
5 3
1
2
8
4
9
와 같을 때 출력으로 아래와 같이 리스트 내 원소로 담기기 때문에 숏코딩의 예시와 같이 변수를 할당할 수 있다.
['5', '3', '1', '2', '8', '4', '9']
나머지 로직은 완전 똑같다.