[투포인터] Parametric Search / 최대 거리의 점

문제링크

https://www.codetree.ai/missions/8/problems/maximum-distance-point?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 서로 다른 n개의 점에 대해서 m개의 물건을 설치할 때, (설치된 물건 사이의 거리의 최솟값)의 최댓값을 찾아라!
• n이 최대 200,000이므로 완탐 등은 불가능!!
  • 이분탐색 → 이분탐색으로 선택할거면, 어떤 변수가 이분탐색의 대상이 될 수 있는지에 대해서 고민을 해야한다.
  • 누적합
  • 그리디...
• 예시를 보면서 이해를 해봅시다. 설치할 물건의 수는 3개이다.

인접한 두 물체 사이의 최소거리	1(반드시 설치)	5	12	21
1	o	o	o	o (4개 설치 가능) T
2	o	o	o	o (4개 설치 가능) T
...				T
8	o	x	o	o (3개 설치 가능) T
9	o	x	o	o (3개 설치 가능) T
10	o	x	o	x (2개 설치 가능) F

• T / F → Parametric Search
• x좌표: 최소거리(dist) → get_count(mid) >= target →  l = mid + 1, ans = mid
  • 왼쪽구간이 정답이다. ans는 l과 깉이 있어야 한다.
  • target을 만족시키는 최대 mid를 구해야한다. l을 최대한 올려야한다.

2. 코드(Python)

n, m = map(int, input().split())
points = [int(input()) for _ in range(n)]
points.sort()
# 두 점 사이의 최소거리를 변수로 분다!
def get_count(dist):
    # 가장 왼쪽은 반드시 설치
    # 두 인접한 사이의 거리의 최솟값이 dist일 때 설치할 수 있는 곳의 수
    # 처음 기준은 맨 왼쪽..
    # 왼쪽1 왼쪽2 ....
    # 왼쪽1과 왼쪽2의 차이가 최소거리보다 작아
    # 왼쪽1 왼쪽2 왼쪽3 과 비교해여함.
    # 기준은 왼쪽이 1이 된다.
    # 착각: 무조건 서로 인접한 것들의 차이를 구하는 것은 아니다!
    cnt = 1
    standard = points[0]
    for i in range(1, n):
        if abs(points[i] - standard) >= dist:
            cnt += 1
            standard = points[i]

    return cnt


def binary_search(target):
    # 거리
    l, r = 1, max(points)
    ans = -1
    while l <= r:
        mid = (l + r) // 2
        if get_count(mid) >= target:
            ans = mid
            l = mid + 1
        else:
            r = mid -1

    return ans

print(binary_search(m))