[백준] 2230번 수 고르기 - Python

이번에 해결해 볼 문제는 백준에 있는 2230번 수 고르기입니다.

---

문제 설명

• N개의 정수로 이루어진 수열에서 두 수를 골랐을 때 그 차이가 M 이상이면서 제일 작은 차이를 구하면 됩니다.
• 단, 시간 제한은 2초입니다.

문제 해결 아이디어

• 이전에 풀어봤던 Two-Point 문제와 다른 점이 있다면 주어진 수열의 숫자가 정수라는 점과 합이 아닌 차이를 구하는 문제라는 점입니다.
• 합이 아닌 차이를 기준으로 인덱스를 가리키는 두 개의 포인트를 움직여야합니다.
  • 차이를 기준으로 포인트를 이동시키기 위해서는 한 가지 과정을 필수적으로 수행해야합니다.
  • 바로 주어진 수열을 정렬시키는 것입니다. 수열을 정렬 시켜야만 두 수의 차이가 증가할 것인지 감소할 것인지 알 수 있기 때문입니다.
  • 이 부분만 잘 해결할 수 있다면 해당 문제는 쉽게 해결할 수 있습니다.

문제 해결 코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(int(input()))

arr.sort()
start, end = 0, 0
diff = 2000000000

while 0 <= start < N and 0 <= end < N:
    val = abs(arr[start] - arr[end])
    if val >= M:
        diff = min(diff, val)
        start += 1
    else:
        end += 1

print(diff)