[백준 2230] 수 고르기(Python)

1. 아이디어

문제에서 요구하는 것은 수열에서 두 수를 선택했을 때, 차이가 M이상이면서 제일 작은 경우를 구하는 것이다. 두 수를 선택하는데 있어, 수열의 형태는 중요하지 않다. 따라서 정렬 후, 문제 유형에서 제시된 것 처럼 투 포인터로 해결한다. 주의해야할 점은 같은 수를 고르는 경우도 있다는 것이다. 예를 들어, N=1일 때, 수를 2번 뽑는 경우이다. 1개의 정수를 2번 선택해서 차이를 구한다. 다시 말해, 수열을 배열(arr)로 표현할 때, 좌측 포인터(lp), 우측 포인터(rp)를 같은 인덱스에 두고, 동일한 곳을 가리키고 있는 수의 차이도 고려해야한다.(물론 결과는 0)

만약 차이가 M이상일 경우, 사전에 수열을 정렬시켰기 때문에, rp가 가리키는 곳 이후들은 고려하지 않아도 된다. 왜냐하면 우리가 원하는 것은 차이가 M이상이면서 제일 작은 경우를 구하는 것이기 때문이다. 따라서 lp가 다음 수를 가르키게하고, lp가 가르킨 곳을 rp도 가르키게한다.

만약 차이가 M미만일 경우, rp가 다음 수를 가르키게한다. 차이가 M이상이 될 때까지 반복하고 rp가 N이 되는 순간, lp가 다음 수를 가르키게하고 rp도 lp가 가르킨 곳을 가르킨다.


위의 과정들을 lp가 N이 될 때까지 반복한다. 그리고 차이가 M이상이면서 그 차이가 가장 적은 것을 선택하면된다.

2. 코드

import sys

n, m = map(int, sys.stdin.readline().rsplit())
arr = []
for _ in range(n): arr.append(int(sys.stdin.readline().rstrip()))

arr.sort()
lp, rp = 0, 0
answer = int(2e9)

while lp < n:
    diff = abs(arr[lp]-arr[rp])
    if diff >= m:
        answer = min(answer, diff)
        if diff == m : break
        lp += 1
        rp = lp
        continue

    rp += 1
    if rp == n:
        lp += 1
        rp = lp

print(answer)