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

www.acmicpc.net/problem/2230

2230번: 수 고르기

 

문제풀이

N, M : 입력값

arr : 입력 배열

 

투 포인터(left, right)를 이용하여 해결할 수 있다.

 

1. 배열(arr)을 입력받고 정렬을 해준다.

- 정렬을 하지 않으면 투 포인터를 정상적으로 사용할 수 없다.

 

2. left, right 를 이용하여 arr[right] 에서 arr[left]를 뺀다(이 값을 tmp 변수에 저장).

- tmp가 M보다 작을 경우는 두 값의 차이를 늘려줘야 하므로 right를 1 증가시킨다.

- tmp가 M일 경우, 조건에 충족(M보다 크면서 두 값의 차이가 가장 작은 경우)하면서 가장 작은 값이기에 바로 M을 출력한다.

- tmp가 M보다 클 경우, 가장 적은 차이를 찾아야 하기 때문에 left를 1 증가시키면서 가장 적은 차이를 찾아낸다.

 

3. 결과(ans)를 출력한다.

 

 

코드

import sys

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    arr = [0] * N
    for i in range(N):
        arr[i] = int(sys.stdin.readline().rstrip())
    arr.sort()
    left, right = 0, 1
    ans = sys.maxsize

    while left < N and right < N:
        tmp = arr[right] - arr[left]
        if tmp == M:
            print(M)
            exit(0)
        if tmp < M:
            right += 1
            continue
        left += 1
        ans = min(ans, tmp)
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!