[ 2230 ] [ Two-Pointer ] 수 고르기

문제 설명

---

문제

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.

예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.

출력

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

제한

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ 2,000,000,000
• 0 ≤ |A[i]| ≤ 1,000,000,000

---

풀이 과정

1. 수열을 오름차순으로 정렬한다.
2. left, right를 0, 0으로 두고 시작.
   • array[right] - array[left]의 값에 따라 진행
   • M 이상이라면 left를 한칸 올린다.
   • M 이하라면 right를 한칸 올린다.
   • 이 때, left가 right보다 커질수도 있으니, 그러한 경우는 right도 한칸 올려서 맞추어 줌.
   • 진행하면서 array[right] - array[left] >= M인 경우 차이값의 최솟값 저장
3. 최솟값을 출력해주면 된다.

---

소스 코드

---

import sys

input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
array = [int(input().rstrip()) for _ in range(N)]

array.sort()
a, b = 0, 0
answer = int(10e9)
while b < len(array):
    subtraction = array[b] - array[a]

    if subtraction >= M:
        answer = min(answer, subtraction)

    if subtraction <= M:
        b = b + 1
    else:
        a = a + 1

    if a > b:
        b = b + 1

print(answer)