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

문제

https://www.acmicpc.net/problem/2230

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이상인 두 수를 고를 수 있다.

---

Algorithm

차의 최솟값을 확인해야 하므로 투 포인터를 이용해 인덱스 0 부터 인덱스를 늘려가며 탐색한다

리스트를 오름차순으로 정렬해 탐색이 용이하게 한다

투포인터 탐색 중 left 값이 right 값보다 높아져 오류가 생길 수 있으므로 left가 right 보다 클 경우 right = left를 실행해 오류가 발생하지 않도록 한

 

---

 

 

Code

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
lst = sorted([int(input()) for _ in range(N)])
left, right = 0, 0

least = float('inf')

while right < N:
    temp = lst[right] - lst[left]
    if (temp < M):
        right += 1
    else:
        least = min(least, temp)
        left += 1
        
    if left > right:
        right = left

print(least)