[백준] 2230: 수 고르기 - JAVA

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

 

풀이

n개의 정수가 주어지고, 두 수를 골랐을 때 차이가 m 이상인 경우 중 제일 작은 경우를 골라야 한다.

정렬을 해놓고 슬라이딩윈도우를 통해 두 수를 골라 차이를 비교했다.

start, end 이렇게 두 포인터를 두고 두 수의 차이가 m보다 작은 경우 end를 1 늘린다.

두 수의 차이가 큰 경우 정답을 갱신하고 start를 1늘린다.

 

---

 

메모리: 28584KB
시간: 396ms
언어: Java 11

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        int start = 0;
        int end = 0;
        int answer = Integer.MAX_VALUE;
        while (start <= end && end < n) {
            int dist = arr[end] - arr[start];

            if (dist < m) {
                end++;
            } else {
                answer = Math.min(answer, dist);
                start++;
            }
        }

        System.out.println(answer);
    }

}