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

문제

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

import sys
sys.stdin = open("input.text", "rt")

n,m = map(int, input().split())
data = []
for _ in range(n):
    data.append(int(input()))
data.sort()
res = int(2e9) # 차이가 m 이상이면서 가장 작은 경우를 기록하기 위해

e = 0
for s in range(n):
    # 차이가 m보다 작으면 끝점을 증가시켜서 차이를 키워
    while e < n and data[e] - data[s] < m:
        e += 1
    if e < n and data[e] - data[s] >= m: # 반복문 탈출 시 끝점과 시작점 값 차이가 m 이상.
        res = min(res, data[e] - data[s])
    else:
        break
print(res)

코멘트

중요한게 제한을 잘 봤어야 했다.
m의 최댓값이 2e9이기 때문에 초기값을 1e9로 하면 틀렸다고 나온다...

최대, 최소에 대한 제약을 범위를 잘 보자.