[백준/Python] 2230 수 고르기

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

2230번: 수 고르기

# 풀이

일반적인 이중포문으로 생각하고 돌리면 쉽지만, 시간 초과가 난다. 이럴 때 사용하는것이 투포인터인데, 투포인터를 사용하여 시간복잡도를 줄이면 된다.

m=3이고 배열 1,2,3,5,4 라고 생각했을 때, 먼저 정렬을 해준다. 그러면 1,2,3,4,5인데 이때, 두수를 비교해보자

1과 1: 차이가 0이므로 틀림. 1과 2: 차이가 1이므로 틀림. 1과 3: 차이가 2이므로 틀림. 1과4: 차이가 3이므로 가능하다. 

m보다 큰 가장 작은 수들을 찾는것이 목적이므로 그 수는 m과 같은 3이 될것이고, 3보다 크면서 3보다 작은 수는 3밖에 없다.

이제 조건을 생각해보자

비교하는 두 수를 각각 left, right라고 하자

반복문의 기준은 left가 right보다 작고, 이 두수는 n 보다 항상 작으면 된다.

조건문의 기준은 두 수의 차가 m보다 작을 경우와 클 경우를 생각해 보면된다.

m보다 작을 경우, right를 오른쪽으로 넘기면 되고, m보다 클경우는 조건에 부합하므로 저장을 한다.

그리고 이 저장한 값과 원래 기준 값의 최소값을 비교하여 m보다 크면서 가장 작은 최소값을 출력하면 된다.

# 코드

n,m=map(int,input().split())

arr=[]
for _ in range(n):
    arr.append(int(input()))
arr.sort()


mins=2e9

left,right=0,0
while left<=right and right<n:
    if arr[right]-arr[left]<m:
        right+=1
    else:
        mins=min(mins,arr[right]-arr[left])
        left+=1
    
print(mins)