[백준] 2110 공유기 설치 in Python

나의 시간 초과 코드 ㅋㅋㅋㅋ 답은 나오는데....비효율적이라는 거지

# 2110 공유기 설치
from itertools import permutations

n,c = map(int, input().split())
array = []
for i in range(n):
    array.append(int(input()))

result = 0
array.sort() # 탐색을 위해 정렬하기

for case in permutations(array, c):
    temp = n
    for i in range(c-1):
        temp = min(temp, case[i+1]-case[i])
    result = max(temp, result)
print(result)

 

이 문제의 유형은 이진탐색이다 .. 이진탐색 !!! 

즉, '최대 인접 거리' 를 start ~ end 범위 내 에서 이진탐색으로 찾는 것이다. 

그리고 mid 는 현재 확인중인 최대 인접거리가 된다. 

mid 간격 만큼 공유기를 설치 했을 때 c개 이상 설치 할 수 있으면 그 값을 result에 저장한다. 그리고 start를 mid+1로 갱신하여 더 큰 간격이 있는지 확인한다.

mid 간격 만큼 공유기를 설치 했을 때 c개 이상 설치 할 수 없으면, end 의 범위를 mid-1로 갱신하여, 탐색의 범위를 제한한다.

탐색은 while문의 조건 start <= end 일 때까지 반복하며 가장 큰 값을 저장하면 된다.

# 2110 공유기 설치


n,c = map(int, input().split())
array = []
for i in range(n):
    array.append(int(input()))
array.sort()
start = 1 # 최소 간격
end = array[-1] - array[0] # 최대 간격
result = 0

while start <= end:
    mid = (start+end)//2 # 4
    count = 1 # 공유기 개수
    value = array[0]
    for i in range(1, n):
        if array[i] >= value + mid:
            value = array[i]
            count += 1
    if count >= c:
        start = mid+1 # 될 수 있는 더 큰 간격이 있는지 호가인 
        result = mid
    else:
        end = mid - 1

print(result)