문제 이해

숫자 배열에서 2개의 수 A,B를 선택하자.
이 때, A - B의 차이가 M 이상인 모든 (A,B) 중 최소의 (A-B) 값을 구하는 문제이다.
(무조건 한 개의 (A,B) 쌍은 존재한다.)

---

문제 풀이

A - B = C
A가 증가한다면 C 값은 증가할 것이고, B가 증가한다면 C값은 감소할 것이다.

먼저 숫자 배열을 Sorting 시킨다.
이후 A를 위한 포인터 left, B를 위한 포인터 right을 준비한다.
이후 아래와 같이 포인터를 이동시킨다.

1. arr[right] - arr[left] >= M : 정답이 될 수 있는 가능성이 존재한다.
   arr[right] - arr[left]의 최솟값을 구하고 싶기 때문에 left를 1증가시켜 A - B를 감소시켜 본다.

2. arr[right] - arr[left] < M : 정답이 될 수 없다. A - B가 커져야 하므로 right을 1 증가시킨다.

수열에서 같은 수를 고를 수도 있다고 하였다. 하지만, left > right일 수는 없다.
이 때, left > right인 경우는 left = right, 즉 arr[right] - arr[left] = 0이 되어 left가 1증가하는 경우 밖에 존재하지 않는다.
따라서, left > right일 경우 right을 1 증가시켜 left > right이 되지 않도록 조절해준다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int N;
	static Long M;
	static Long[] A;
	
	static void two_pointer() {
		int left = 0;
		int right = 0;
		long ans = Long.MAX_VALUE;
	
		while(right < N) {
			long minus = A[right] - A[left];
			
			if(minus>=M) {
                // 정답이 될 수 있는 후보
                // 이전에 저장된 ans와 구한 minus 값 중 최소값으로 ans 갱신
                // A - B값을 감소시켜 재확인 해야 하므로 left를 1 증가시킴
				ans = Math.min(ans, minus);
				left++;
			}
			else {
                // 정답이 될 수 없음
                // A - B가 증가해야 하므로 A를 증가시키고, 
                // 따라서 right을 1 증가시킴
				right++;
			}
			
			if(left>right) {
                // 문제 풀이 참조
				right++;
			}
		}
		
		System.out.println(ans);
		
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		M = sc.nextLong();
		A = new Long[N];
		for(int i =0;i<N;i++) {
			A[i] = sc.nextLong();
		}
		
		Arrays.sort(A); // 이 문제의 핵심 부분. Sorting!!!
		
		two_pointer();
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

1 0

0

답 : 0

3 0

1

2

3

답 : 0

• 개인적으로 이 문제는 백준의 테스트 케이스가 그렇게 좋지는 않다. 따라서 맞았습니다를 받았더라도 위 2개까지 맞았는지 확인하면 좋을 것 같다. 문제는 left = right인 경우도 포함시킨다고 하였지만, 내가 생각할 때는 Test Case에 그런 문제가 존재하지 않는 것 같다. 또한 array의 길이가 1인 경우도 test case에 누락되어 있는 것 같다.

​