백준 2230 : 수 고르기 (Python)

본문 링크

import sys
input=sys.stdin.readline

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

L=[]

for i in range(N):
    L.append(int(input()))

L.sort()

start=0 ; end=1 ; answer=2000000000

while start<=end and end<N:

    if L[end]-L[start]<M:
        end+=1
    elif L[end]-L[start]>=M:
        answer=min(answer,L[end]-L[start])
        start+=1

print(answer)

📌 어떻게 문제에 접근할 것인가?

두 수의 차이가 $M$ 이상이면서 제일 작은 값을 찾는 문제이다.

$N$ 의 범위를 보면 $1 ≤ N ≤ 100,000$ 이고 두 수의 차이를 묻는 문제이기 때문에
$O(N)$ 으로 탐색가능한 투 포인터를 사용하였다.

📌 투 포인터를 어떻게 사용할 것인가?

먼저 리스트 $L$ 을 입력받고 정렬해준다. 이후 start 와 end 를 0 과 1 로 잡아준후 answer=2000000000 으로 잡아준다.

만약 두 수의 차이가 $M$ 보다 작을경우 end 를 증가시키고 $M$ 보다 크거나 같을경우
answer 값을 자기자신과 두 수의 차이중 더 작은값으로 적용해준다. 이후 start 값을 증가한다.

✅ 코드에서 주의해야할 부분

• while 문 조건은 start<=end 와 end<N 으로 잡아준다.
• answer 값을 먼저 변경한 후에 start 를 1 증가시킨다.
• answer 값은 2000000000 으로 잡는다.
• 리스트 $L$ 은 정렬해준다.