[백준] 2230 수 고르기 (파이썬 python)

 

 

문제 링크

 

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

2230번: 수 고르기

 

 

문제 풀이

 

투 포인터 개념을 활용해야 하는 문제입니다.

해결의 핵심 포인트는 주어진 숫자 배열을 오름차순 정렬한 후,

왼쪽 기준점을 인덱스 1씩 늘려가며 고정하고 오른쪽에 있는 수들과의 차이를 확인하는 것입니다.

오른쪽 기준점은 고정된 왼쪽 기준점과 다르게 1씩 오른쪽으로 이동하며

왼쪽 기준점과의 차이를 확인하는데 사용됩니다.

만약 두 수의 차이가 주어진 m보다 작을 경우 right을 오른쪽으로 옮겨 m 이상의 차이를 도출해내야 합니다.

만약, 두 수의 차이가 m보다 클 경우 현재의 최소 차이값과 비교하여 더 작은 수로 갱신하여 줍니다.

만약 정확히 m만큼 차이가 나는 두 수가 있을 경우 더 확인하지 않고 m을 결괏값으로 갱신하고 중단합니다.

보통 최솟값을 갱신하는 연산을 할 때 초기값을 1e9값으로 두는 경우가 많았으나,

해당 문제에서는 m의 범위가 2,000,000,000까지이므로

해당 범위까지로 초기화해야 정상적으로 답을 도출할 수 있습니다.

 

 

전체 코드

 

n, m = map(int, input().split())
nums = [int(input()) for _ in range(n)]
nums.sort()
left, right = 0, 0
result = 2000000000
while right < n:
    diff = nums[right] - nums[left]
    if diff < m:
        right += 1
    elif diff > m:
        result = min(result, diff)
        left += 1
    else:
        result = m
        break
print(result)