[SWEA] 공평한 분배 2

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AY6cg0MKeVkDFAXt&categoryId=AY6cg0MKeVkDFAXt&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
            int K = sc.nextInt();
            ArrayList<Integer> candies = new ArrayList<Integer>();

            for(int i = 0; i < N; i++) {
                candies.add(sc.nextInt());
            }

            Collections.sort(candies);
            int minDifference = Integer.MAX_VALUE;

            for(int i = 0; i <= N - K; i++) {
                int difference = candies.get(i + K - 1) - candies.get(i);
                minDifference = Math.min(minDifference, difference);
            }

            System.out.println("#" + test_case + " " + minDifference);
        }
    }
}

 

 <실패 사례>

1. N, K간 차이가 홀수인 경우, 짝수인 경우로 나눠서 리스트의 양 끝에서 좁혀온 값의 차이를 구하는 식으로 했는데 그런 식으로는 풀리지 않는다.

 2. 리스트의 양 끝값을 차이만큼 제거한다음 다시 최댓값 최솟값으로 빼면 되긴 하는데 그건 이제 런타임 오류를 발생시킨다.

 

 정렬은 하되, 예를 들면 N번째 사탕주머니랑 N+K 사탕주머니의 차이가 결국 그 범위 내 최대의 차이면서 그 중의 최소를 찾는 방식이라는 점을 인지하고 그대로 구현하면 된다. 초기값을 MAX_VALUE로 최댓값 지정해 주고.. 저번 D2 모 문제에서 범위를 넘어서는 경우도 나왔지만 그러면 어차피 알게 될 것이다..