SWEA 20728. 공평한 분배 2

주어진 N개의 자연수들을 K명에게 나누어줄 때, 최솟값과 최댓값의 차이의 최솟값을 구하는 문제이다.

 

자연수들을 정렬한 후, 처음부터 연속된 K개를 가진 구간을 뒤로 이동하면서 구간 내에서의 최댓값과 최솟값의 차이가 가장 작은 값을 찾는다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int tc=1; tc<= T; tc++) {
            sb.append('#').append(tc).append(' ');
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken());
            int[] board = new int[n];
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++) board[i] = Integer.parseInt(st.nextToken());
            Arrays.sort(board);
            int start = 0, end = k-1;
            int diff = Integer.MAX_VALUE;
            while(end < n) {
                diff = Math.min(diff, board[end] - board[start]);
                end++;
                start++;
            }
            sb.append(diff).append('\n');
        }
        br.close();
        System.out.print(sb);
    }
}