[BOJ] 2230. 수 고르기 (🥇, 투 포인터)

🔗

풀이

수열을 정렬했을 때 두 수 사이의 간격이 M 이상이라면 구할 수 있는 차이 값을 업데이트 한다. 이때 왼쪽에 있는 수 A 라고 했을 때 이제 B 뒤에 있는 수들은 차이 값이 현재 구한 B - A 라는 차이 값 이상이 되기 때문에 더 이상 구하는 의미가 없다. 이때는 이제 A 의 값을 오른쪽으로 한 칸 이동시킨다. 이렇게 되면 이제 옮겨진 A' 라는 값과 B 의 새로운 차이를 구하게 되는데 이 차이는 A의 값이 증가했을 것이므로 이전에 구한 B - A 보다 더 작은 차이가 될 수 있다. 이때 이 값이 M 이상이면 다시 업데이트를 한다.

만약 B - A 가 M 보다 작은 값이라면 사이의 차이를 크게 해야 하므로 이때는 B 의 값을 증가시킨다.

1. 두 수 사이의 차이가 M 보다 크다면 A 를 오른쪽으로 한 칸 이동
   1-1. 이때 두 수 사이의 차이는 가장 작은 값으로 업데이트
2. 두 수 사이의 차이가 M 보다 작다면 B 를 오른쪽으로 한 칸 이동

1, 2 과정을 반복한다.

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

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long M = sc.nextLong();
        
        long[] sequence = new long[N];
        for (int i = 0; i < N; i++) {
            sequence[i] = sc.nextLong();
        }

        int left = 0;
        int right = 0;
        Arrays.sort(sequence);
        long minGap = Long.MAX_VALUE;
        while (left <= right && right < N) {
            System.out.println(left + " " + right);
            long gap = sequence[right] - sequence[left];
            if (gap < M) {
                right++;
                continue;
            }
            
            minGap = Math.min(minGap, gap);
            left++;
        }
        System.out.println(minGap);
    }
}