문제 : https://www.acmicpc.net/problem/2230

문제 요약

• [1, 5, 3] 에서 두 숫자를 골라 차이를 구하는 모든 경우의 수는 다음과 같다.
  • (1, 5) : 5 - 1 = 4
  • (1, 3) : 3 - 1 = 2
  • (5, 3) : 5 - 3 = 2
  • (1, 1), (3, 3), (5, 5) : 0
• 이 중 문제 예시에서 주어진 M = 3이상이면서, 차이가 가장 작은 경우는 4이다.
• 이렇게 주어진 수열에서 구할 수 있는 M 이상의 차이 값 중 최소값을 구해 출력하면 된다.

풀이

정렬

예시
A = [5, 3, 9, 10, 1]
M = 3

• 우선 수열을 정렬할 필요가 있다.

정렬 안했을 때

예를들어 5를 기준으로 나머지 값들과 비교해가면서 차이를 구한다고 했을 때

• 5 - 5 = 0
• 5 - 3 = 2
• 5 - 9 = -4
• 5 - 12 = -7
• 5 - 1 = 4

이렇게 나오는 값이 뒤죽 박죽이라 모든 경우의 수를 탐색해야하고 \(O(N^2)\) 의 탐색을 거쳐야 한다. 또한 결과가 양수일지 음수일지 알 수 없어 abs()를 씌워줘야 한다.

정렬 했을 때

수열을 정렬한다면 [1, 3, 5, 9, 12]의 형태가 되는데, 1을 고정하고 나머지 수와 차이를 구할 때

• 1 - 1 = 0
• 3 - 1 = 2
• 5 - 1 = 4 -> 4 저장

여기까지만 계산하면 된다. 왜냐하면 이미 주어진 M = 3보다 차이가 커진 상황이고, 배열이 오름차순 정렬되어있기 때문에 뒤의 수를 탐색해 봤자 차이가 더 커질 것이기 때문이다.

현재 찾은 ‘M보다 큰 최소값’인 4를 저장하고 다음 순서로 넘어간다.

---

1 다음 위치인 3에서 마지막 탐색시점부터 탐색하면 된다.

• 5 - 3 = 2
• 9 - 3 = 6

6이 M보다 크기 때문에 다음 순서로 넘어간다. 이 때, 기존에 저장된 정답인 4보다 작다면 갱신해주는 절차가 필요하다.

---

지금부터는 같은 알고리즘을 반복한다.

• 9 - 5 = 4
• 10 - 5 = 5
• 12 - 5 = 7
• 12 - 9 = 3 -> 3 저장

12가 마지막 인덱스이므로 더이상 탐색하지 않고 종료하면 된다. 이 경우 시간복잡도는 \(O(N logN)\) 이다.

구현

• 앞서 설명할 때 숫자 하나를 고정시켜놓고 수열을 탐색한다고 했었는데, 이것이 투 포인터이다.

• 편의상 고정되는 값을 left, 탐색하는 값을 right라고 하자.

• 두 수의 차이는 diff = A[right] - A[left]로 정의할 수 있다.
  • diff가 M보다 작다면 더 큰 수와의 차이를 구해야하므로 right를 한 칸 전진한다.
  • diff가 M보다 크다면 diff가 작아져야 하므로 left를 한 칸 전진한다.
  • 이렇게 해주면 앞서 설명한 알고리즘을 구현할 수 있다.
• 마지막으로 IndexError를 막기 위해 right가 수열의 인덱스를 벗어날 경우 탈출하도록 한다.

코드

import sys
input = sys.stdin.readline

def solution(A, N, M):
    left, right = 0, 0
    answer = 2000000000
    while right < N:
        diff = A[right] - A[left]
        if diff < M:
            right += 1
        elif diff > M:
            answer = min(diff, answer)
            left += 1
        else:
            return M
    return answer    

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

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

# 오름차순 정렬
A.sort()

# 답변 구하기
answer = solution(A, N, M)

print(answer)