[백준 2230] 수 고르기 : 투포인터 (python / 파이썬)

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

투 포인터(Two Pointer)

• 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘
• N개의 원소를 가진 배열에서 특정 조건을 만족하는 연속적인 원소들의 집합을 O(N)에 구하는 알고리즘

문제 풀이 아이디어)
① 정렬의 시간 복잡도를 O(N^2) -> O(N)으로 낮추기 위해, 배열을 오름차순으로 정렬한 뒤 투 포인터를 이용

② 예를 들어 1, 5, 45, 90, 200, 300 이라는 배열이 있을 때 차이가 "50" 이상을 찾고 싶으면 "1, 90"의 차이인 89에서 멈추고 "1, 200", "1, 300"은 차이를 계산할 필요가 없음 (최소성을 보장) 이 전까지는 while문을 돌며 end 포인터 +1 하다가, 차이가 M을 넘으면 while 문을 탈출하여 최솟값을 result에 저장 후 start 포인터 + 1

③ for 문 마지막 줄에서 end 값을 1을 빼주는데, while 문 빠져 나올 때 end 포인터가 가리키는 값의 1만큼 늘어서 탈출하기 때문

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

A = []
for i in range(N):
    A.append(int(input()))
A.sort()

tmp = 0
end = 0
result = 1e13

# start를 차례대로 증가시키며 반복
for start in range(N):
    # end를 가능한 만큼 이동시키기
    tmp = A[end] - A[start]
    
    while (tmp < M and end < N):
        tmp = A[end] - A[start]
        end += 1
    
    if tmp >= M:
        result = min(result, tmp)
        
    end -= 1
    
print(result)