Python/코딩테스트
[백준] 2330번 : 수 고르기
edoyyoy
2023. 9. 23. 09:54
2230번: 수 고르기
N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어
www.acmicpc.net
✓ 문제 풀이 : 투포인터 알고리즘
수가 크기 때문에 반복문을 1번만 사용해야한다.
투포인터 알고리즘으로 탐색하면 빠르게 수를 고를 수 있다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [int(input()) for _ in range(n)]
a.sort()
s, e = 0, 1
res = float('inf')
while s <= e and e < n:
tmp = a[e]-a[s]
if tmp < m:
e += 1
else:
res = min(res, tmp)
s += 1
if tmp == m:
break
print(res)