[백준] 2230) 수 고르기 - Gold 5

[jusung-c]

문제 링크

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

문제 조건

• N개의 정수로 이루어진 수열 A (1 ≤ N ≤ 10만)
• 차이가 M 이상이면서 제일 작은 경우를 구하라 (0 ≤ M ≤ 20억)
• 0 ≤ 각 원소의 절댓값 ≤ 10억

---

아이디어

1. 수열 오름차순 정렬
2. L, R 포인터를 왼쪽에서부터 시작해 차이가 M 이상이 될 때까지 R을 이동 후 최솟값 갱신
3. L을 이동 후 위 과정 반복

---

시간 복잡도

O(N)

---

구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br;
    static StringTokenizer st;
    static int N, M;
    static int[] arr;

    public static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
    }

    private static void pro() throws IOException {
        Arrays.sort(arr, 1, N + 1);

        int R = 0;
        int diff = 0;
        int min = Integer.MAX_VALUE;

        for (int L = 1; L <= N; L++) {
            if (R != 0) {
                diff = arr[R] - arr[L];
            }

            while (R + 1 <= N && diff < M) {
                R++;
                diff = arr[R] - arr[L];
            }

            if (diff >= M) {
                min = Math.min(min, diff);
            }
        }

        bw.write(min + " ");

    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}