[BOJ] 2230. 수 고르기

📌 문제 제목

문제 링크: BOJ 2230

---

🗒️ 문제 설명

N개의 정수로 이루어진 수열이 있을 때, 이 수열에서 두 수를 골랐을 때 그 차이가 M 이상이면서 제일 작은 경우를 구하여라.

시간 제한: 2초

메모리 제한: 128MB

1 <= N <= 100,000

0 <= M <= 2,000,000,000

0 <= |A[i]| <= 1,000,000,000

---

💡 문제 해결 아이디어

• N이 최대 100,000 이기 때문에 O(N log N) 이하의 시간복잡도를 가지는 알고리즘 사용
• 정렬을 시킨다면 st가 증가할 때 en이 줄어들 수 없으므로 O(N)의 시간복잡도를 가지는 투 포인터를 사용할 수 있다.
• 입력이 정렬되어 있지 않으므로 수를 정렬 - O(N log N)
• st를 0으로 잡고 두 수의 차가 M 이상일 때까지 en을 증가시킴.
• 처음 M 이상인 지점에 두 수의 차를 answer과 비교

---

⌛️ 시간 복잡도

• O(N log N)
• 정렬에 O(N log N)
• 투 포인터에 O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

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

en = 0
answer = float("inf")

seq.sort()

for st in range(N):
    while en < N and seq[en] - seq[st] < M:
        en += 1

    if en == N:
        break

    answer = min(answer, seq[en] - seq[st])

print(answer)