백준 20917 : 사회적 거리 두기 (Python)

본문 링크

import sys
input=sys.stdin.readline

T=int(input())

for i in range(T):
    N,S=map(int,input().split())
    L=sorted(list(map(int,input().split()))) #정렬해야함.
    start=1 ; end=max(L)
    while start<=end:
        mid=(start+end)//2
        left=L[0] ; count=1
        for i in range(1,N):
            right=L[i]
            if abs(right-left)>=mid:
                count+=1
                left=L[i]
        if count>=S:
            start=mid+1
        else:
            end=mid-1
    print(end)

📌 어떻게 접근할 것인가?

먼저 문제에서 주어지는 범위를 보면
1 ≤ T ≤ 10 , 2 ≤ s ≤ n ≤ 200,000 이다.
즉 완전탐색처럼 O(N^2) 으로 풀면 시간초과가 난다.

문제에서 가장 가까운 두 좌석의 거리의 최대값을 구하고자 하므로
이분탐색을 사용하도록 한다.

📌 어떻게 이분탐색할것인가?

일단 리스트를 입력받고 꼭 정렬해주어야한다.
이후 start=1 , end=max(L) 로 잡아준후
두 거리의 차이를 left 와 right 변수를 활용해준다.
리스트 값은 입구로부터의 거리이기 때문에
right-left 값이 mid 값보다 크거나 같으면 콘센트를 꽂은 위치의 개수(count) 를 1 증가시킨다.

이후 count 변수가 s 보다 크거나 같으면 mid 값이 작아 콘센트를 많이 꽂았으므로 start 변수를 증가시킨다.

마지막으로 가장 가까운 두 좌석의 최대값을 구하는 것이므로
end 를 출력한다.

✅ 코드에서 주의해야할 점

• 리스트를 정렬해준다.
• 매번 right 위치를 L[i] 로 값을 변경해준다.
• count 는 1 로 시작한다. 처음에 right-left>=mid 이면 좌석 2 개를 선택하기 때문이다.
• pypy 로 제출해야지 시간초과가 나지 않는다.