[Baekjoon 2230 / Python / 골드5] 수 고르기

문제

import sys

input = sys.stdin.readline

INF = int(2e9)

N, M = map(int, input().split())

number = [int(input()) for _ in range(N)]

number.sort()

def twoPointer():

    result = INF

    start = 0

    end = 1

    while end < N:

        if number[end] - number[start] >= M:

            result = min(result, number[end] - number[start])

            start += 1

            if start == end:

                end += 1

        else:

            end += 1

   

    return result

print(twoPointer())

 

투 포인터 문제이다. 두 수를 고르되, 두 수의 차이가 M 이상인 것 중 가장 작은 수를 출력하면 된다.

 

먼저 수열을 정렬한다.

start는 0, end는 1로 두고 투 포인터 탐색을 시작한다. start와 end 각각 다른 수를 가리킨다. 두 숫자를 골라야 하니까.

end - start가 M 이상일 경우, 기존 result값과 비교해 더 작은 값을 result로 갱신한다.

 

만약 start와 end가 겹칠 경우, 숫자를 한개만 고르는 상황이 되어 버리기 때문에 end를 1 더해준다. start를 더하면 start가 end 뒤에 오게 되니까 end를 더하는 것.

 

이 문제에서 중요한 점은, 두 수의 차이가 M이상인 경우를 찾았다면 더 이상 start를 그대로 두고 end를 늘려 볼 필요가 없다는 점이다. 왜냐하면 수열은 정렬되어 있고, end를 늘려 더 찾아봤자 두 수의 차이는 커지기만 할 뿐이기 때문이다. 따라서 바로 start를 올려주고 다음 탐색을 시작하면 된다.

 

또한 주의사항이, 숫자 범위를 잘 봐야 한다. 숫자가 최대 10억까지인 줄 알았는데 절댓값으로 쓰여 있었다. 따라서 두 수의 차이는 최대 10억이 아니라 20억이다. 이것 때문에 처음에 INF를 1e9(10억)으로 설정했다가 틀렸었다. 2e9(20억)이상으로 설정해야 문제가 생기지 않는다.

 

결과