[BOJ] 3988. 수 고르기(java)

문제

수열이 주어졌을 때, M을 수열의 모든 두 원소의 차이 중 가장 큰 값이라고 한다. m은 그 차이 중 가장 작은 값이라고 한다.

크기가 N인 수열 V가 주어진다. 여기서 K개 수를 적절히 제거해서 M+m을 가능한 작게 만드는 프로그램을 작성하시오.

입력

첫째 줄에 N(3 ≤ N ≤ 1,000,000)과 K(1 ≤ K ≤ N-2)가 주어진다.

둘째 줄에 V의 원소가 공백으로 구분되어 주어진다. (-5,000,000 ≤ Vi ≤ 5,000,000)

출력

첫째 줄에 가장 작은 M+m을 출력한다.

예제 입력

5 2 -3 -2 3 8 6

예제 출력 

7

풀이

 

참고로 compareTo를 잘못구현하면 런타임 오류가 난다..

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
public class B3988 {
    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 k = Integer.parseInt(st.nextToken());
        int[] data = new int[n];

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

        Deque<DataGap> deque = new ArrayDeque<>(); // 데이터 차이 값을 넣을 큐
        int dataGapUnit = n - k - 1;         //데이터 차이 값을 넣을 큐에서 슬라이딩 할 데이터 개수(범위)
        //슬라이딩 할 데이터 개수(범위)는 n(전체)-k(제거)-1(데이터의 차이를 넣을 것이기 떼문에 개수 하나 줄음)
        int result = data[n - 1] - data[0];

        for (int i = 0; i < n - 1; i++) {
            DataGap d = new DataGap(i, data[i + 1] - data[i]);
            //최소값을 구하는 범위(i-dataGapUnit)를 넘었을 때, 오래된 것 제거하기
            if (!deque.isEmpty() && deque.peekFirst().startIdx <= i - dataGapUnit) {
                deque.removeFirst();
            }

            //새로 들어온 차이 값보다 더 큰 차이값이 있으면 제거 -> 그 범위에서의 최소값을 구할 때 제거된 값은 최소값이 될 수 없으니까
            while (!deque.isEmpty() && deque.peekLast().value > d.value) {
                deque.removeLast();
            }
            deque.addLast(d);

            if (i + 1 >= dataGapUnit) {
                int M = data[i + 1] - data[i + 1 - dataGapUnit];
                result = Math.min(result, deque.peekFirst().value + M);
            }
        }
        System.out.println(result);
    }

    //DataGap은 시작 인덱스(i)와 차이 값으로 구성되어있다.
    private static class DataGap {
        int startIdx;       //data[i]와 data[i+1]가 있을 때 앞에 있는 data의 인덱스가 startIdx
        int value;          //data[i]와 data[i+1의 차이가 value

        public DataGap(int startIdx, int value) {
            this.startIdx = startIdx;
            this.value = value;
        }
    }
}

 

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

3988번: 수 고르기