[BOJ] 2230 - 수 고르기 (Python)

 

 

아이디어

 

투 포인터로 두 수의 차이가 M 이상일 때를 찾는다.

 

 

풀이

 

값의 차이만 알면 되므로 셋으로 입력 값들의 중복을 제거한 후 정렬된 리스트 A로 변환하고 그 길이를 N으로 저장한다.

투 포인터로 두 수의 차이와 M을 비교하며 M을 초과한 경우에 결과값과 비교해 더 작은 값으로 갱신해 나간다.

차이가 M인 경우는 더 이상 탐색할 필요가 없으므로 결과값을 M으로 저장 후 반복문을 종료한다.

 

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
A = set()
for _ in range(N):
    A.add(int(input()))
A = sorted(A)
N = len(A)
s = e = 0
res = A[-1]-A[0]
while s <= e < N:
    if A[e]-A[s] < M:
        e += 1
    elif A[e]-A[s] > M:
        res = min(res, A[e]-A[s])
        s += 1
    else:
        res = M
        break
print(res)