[Two Pointers] 백준 2230번 “수 고르기” Python 풀이

문제 링크

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

풀이

• 투 포인터 알고리즘을 사용해 해결할 수 있습니다.
• 우선, 투 포인터 알고리즘을 사용하기 위해 입력 수열을 오름차순으로 정렬해야합니다.
• 이후, 두 포인터에 위치한 수의 차이에 따라 왼쪽 또는 오른쪽 포인터를 오른쪽으로 한 칸씩 이동하면 됩니다.
• 참고
  • m의 최대값은 2,000,000,000이기 때문에
  • result의 초기값은 int(2e9) 또는 sys.maxsize로 설정해야합니다.

코드

import sys

n, m = map(int, sys.stdin.readline().split())

# 수열 저장
arr = []
for _ in range(n):
    arr.append(int(sys.stdin.readline()))
# 수열 오름차순 정렬
arr.sort()

# 투 포인터 시작 인덱스
left, right = 0, 0

# 두 수의 차이가 M 이상이면서 제일 작은 수
result = int(2e9)

# 투 포인터 탐색 시작
while left <= right and right < n:

    # 두 수의 차이가 M 미만일 경우
    if arr[right]-arr[left] < m:
        # 오른쪽 인덱스를 1 증가
        right += 1

    # 두 수의 차이가 M 이상일 경우
    else:
        # 두 수의 차이가 M 이상이면서 제일 작은 수를 비교한 뒤, 업데이트
        result = min(result, arr[right]-arr[left])
        # 왼쪽 인덱스를 1 증가
        left += 1

# 결과 출력
print(result)