Intuition

N이 최대 20만이므로 두 개씩 잡아가며 거리를 측정해서 수행하는 브루트포스로는 O(N^2)이므로 시간초과일게 뻔하다. 따라서 다른 방안을 선택해야 한다. 가장 간단한 방법은 거리를 미리 정해두고, 그 거리를 만족하는지 검증하는 로직으로 처리하는 것이다. 이는 파라메트릭 서치의 기본 유형이며 다음과 같은 조건을 만족하는지 체크하면 된다.

1. 값을 대입하여 조건을 만족하는지 바로 체크할 수 있나?
2. 정답 후보군이 연속된 숫자 중 하나인가?

이 문제는 값을 만족하는지 체크하는 로직이 정적이며, 정답이 될 수 있는 ‘최대 거리’ 또한 연속된 자연수 중 하나이므로 파라메트릭 서치를 활용할 수 있다. 이렇게 되면 시간복잡도가 O(Nlog1e9)이므로 문제를 풀어낼 수 있다.

Algorithm

1. 정답이 될 수 있는 최대 거리를 이분탐색으로 선정한다.
2. 해당 거리값이 조건에 만족하는지 체크한다.
3. 만족하면 거리를 늘린다. / 만족하지 않으면 거리를 줄인다.

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
li = []
ans = N - 1

for _ in range(N):
    li.append(int(input()))
li.sort()
def can_go(dist):
    cnt = C-1
    prev = 0
    for i in range(1, N):
        if li[i] - li[prev] >= dist:
            prev = i
            cnt -= 1
            if cnt == 0:
                return True
    return False

def ps():
    global ans
    left = 0
    right = 10**18
    while left <= right:
        mid = (left + right) // 2
        if can_go(mid):
            ans = mid
            left = mid + 1
        else :
            right = mid - 1
ps()
print(ans)

Complexity Analysis

• 시간복잡도 : O(N * log 1e9)
• 공간복잡도 : O(N)