[백준/Python] 2230 수 고르기

문제 링크

2230번: 수 고르기

 

문제 풀이

• 처음에는 완전 탐색으로 풀었지만 역시나 시간 초과였다.
• 알고리즘에 투 포인터가 있어서 찾아보니 투 포인터라는 알고리즘이 있어 어떤 알고리즘인지 설명을 본 후 다시 코드를 작성하였다.
• 처음값(start, i)은 0부터 n-1까지이고, end는 1부터 n-1까지 범위의 수이다.
• arr[end]-arr[i] 값이 m보다 작으면 end 값을 1 늘리고, m보다 크거나 같으면 res 값과 비교하여 더 작은 값을 저장할 수 있도록 한다.
• 또한 A[i] 값이 -1000,000,000 ~ 100,000,000 범위인 것을 인지해야 한다. 절대값 표기를 못봐서 최대 차이 값을 잘못 설정했다.

 

전체 코드

import sys

n, m = map(int, sys.stdin.readline().split())
arr = [int(sys.stdin.readline()) for _ in range(n)]
arr.sort()

end = 1
res = 2000000000
for i in range(n):
    while arr[end] - arr[i] < m and end < n-1:
        end += 1
    if arr[end] - arr[i] >= m:
        res = min(res, arr[end] - arr[i])

print(res)