[파이썬] 백준 2230 : 수 고르기(골드5)

[파이썬] 백준 2230 : 수 고르기(골드5)

• https://www.acmicpc.net/problem/2230

---

풀이

방향성 생각

• 입력이 10만 이상이라 $O(N^2)$로는 불가능하다.
• 투 포인터로 제한적인 영역을 탐색하면서 $O(N)$으로 풀어주기.

 

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

N,M = map(int,input().split())

arr = [int(input()) for _ in range(N)]
arr.sort()

l,r = 0,0
answer = float('inf')

while l<=r<N:
    d = arr[r] - arr[l]
    if M <= d:
        answer = min(answer,d)
        l += 1
    else:
        r += 1

print(answer)

코멘트

• while 조건에서, l==r까지는 가능하다.
• 같은 숫자에서 조건을 만족시키고, l+=1로 탈출하면 된다.
• 양 쪽에서 포인터를 조이는지, 같은 지점에서 출발하는지는 더 적은 영역을 탐색하는 것을 생각하면 자연스럽게 알 수 있다.