[ baekjoon ] 2230. 수 고르기

문제

N(1≤N≤100,000)개의 수로 이루어진 수열 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(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다.

출력

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

import sys 
input = sys.stdin.readline
n, m = map(int, input().split())
nums = []
for _ in range(n):
  nums.append(int(input()))

nums.sort()
left, right = 0, 1
result = 2000000000 # sys.maxsize
while left < n and right < n:
  length = nums[right] - nums[left]
  if length == m:
    result = m
    break
  elif length < m:
    right += 1
    continue
  result = min(result, length)
  left += 1

print(result)

첨에 이중 for문 돌렸다가 시간초과..
알고리즘 분류를 보니 두포인터라 되어있어서 어케 포인터를 이동하지 하고 검색했다
이 문제는 복습할 땐 바로 풀 수 있을 듯하다.
다만 result 초깃값을 조심해야한다. 절댓값에서의 차이이기 때문에 2000000000으로 두어야 한다.
또한 while문 조건은 right < n만 해도 통과한다.

2021.02.28 복습

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = []
for _ in range(n):
  arr.append(int(input()))

arr.sort()

result = 2000000001
left, right = 0, 1

while right < n:
  dist = arr[right] - arr[left]
  if dist < m:
    right += 1
  elif dist == m:
    result = m
    break
  else:
    result = min(result, dist)
    left += 1
print(result)

ㅎㅎ 두 포인터 떠올려서 성공
또 차이조건에서 틀리고, while문 조건에서도 한 번 걸렸다.