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

퀵소트를 이용한 문제이다. (퀵 소트에 대해 잘 모른다면 바킹덕님의 정렬에 대한 글을 읽고 오자.)

퀵소트에서 두 개의 포인터를 이용하여 하나의 데이터를 기준으로 삼아 포인터가 가르키는 데이터들과 비교하는데

이 두 데이터를 비교할 때 두 수의 차이가 M 이상이면서 현재의 가장 작은 값보다 두 수의 차이가 더 작다면 이것을 저장해주면 된다.

퀵소트로 배열을 정렬할 때까지 계속 반복해주면 된다.

- java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main{
    static int[] arr;
    static int max = 2000000001;
    static int n,m;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        // 첫 줄 입력받기
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        arr = new int[n];
 
        // 배열 입력받기
        for(int i=0; i<n; i++)
            arr[i] = Integer.parseInt(br.readLine());
 
        quickSort(0, n);
        System.out.print(max);
    }
 
    public static void quickSort(int start, int end){
        if(end <= start+1) return;
 
        int pivot = arr[start];
        int left = start+1;
        int right = end-1;
 
        while(true){
            while(left <= right && arr[left] <= pivot) {
                if(pivot - arr[left] >= m){
                    max = (pivot-arr[left]<max)?pivot-arr[left]:max;
                }
                left++;
            }
            while(left <= right && arr[right] >= pivot) {
                if(arr[right] - pivot >= m){
                    max = (arr[right]-pivot<max)?arr[right]-pivot:max;
                }
                right--;
            }
            if(right < left) break;
 
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        int temp = arr[start];
        arr[start] = arr[right];
        arr[right] = temp;
 
        quickSort(start, right);
        quickSort(right+1, end);
    }
}