SWEA(SW Expert Academy) 20728. 공평한 분배 2 D3

● 문제출처

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

●정리(요약)
사탕이 담긴 주머니 N
i 번째 a 개 사탕이 들어감

k개를 선택하여 나눠 주는데 많은 거와 적은 거 사탕 개수 차이를 최소화하여 구하는 프로그램 작성

<입력>
테스트 케이스 수 T
N K
N개의 주머니

<출력>
차이의 최솟값을 출력

●코드1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
class Solution
{
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb= new StringBuilder();
         
        int T = Integer.parseInt(br.readLine());
         
        for(int i = 1; i<=T; i++) {
             
            st= new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            int [] arr=  new int[N];
            List<Integer> list = new ArrayList<Integer>();
             
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0; j<N; j++) {
                arr[j]=Integer.parseInt(st.nextToken());
            }
             
            Arrays.sort(arr);
             
            int min = Integer.MAX_VALUE;
            for(int j=0; j<N-K+1; j++) {
                min=Math.min(min, arr[j+K-1]-arr[j]);
            }
            sb.append("#").append(i+" ").append(min).append("\n");  
        }
        System.out.println(sb);
 
    }
 
}

● 코드2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
 
class Solution
{
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb= new StringBuilder();
         
        int T = Integer.parseInt(br.readLine());
         
        for(int i = 1; i<=T; i++) {
             
            st= new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            int [] arr=  new int[N];
            int [] S = new int[N];
            List<Integer> list = new ArrayList<Integer>();
             
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0; j<N; j++) {
                arr[j]=Integer.parseInt(st.nextToken());
            }
             
            Arrays.sort(arr);
 
            S[0]=0;
            for(int j =1; j<N; j++) {
                S[j]=arr[j]-arr[j-1];
            }
             
             
            boolean isEnd = true;
            int start =1;
            while(isEnd) {
                int sum = 0;
                for(int k=start; k<K+start-1; k++) {
                    sum += S[k];
                    if(k==N-1) {
                        isEnd=false;
                    }
                }
                start++;
                list.add(sum);
            }
             
            sb.append("#").append(i+" ").append(Collections.min(list)).append("\n");    
        }
        System.out.println(sb);
 
    }
 
}

●느낀 점

코드2를 먼저 풀었는데 왜 이렇게 복잡하게 풀었는지 모르겠다...
코드2는 arr[]를 정렬하고 S[] 에 각각 차이를 구하였다. 그리고 list에 차이를 k만큼 합을 구하여 add하였다.

하지만
코드1 처럼 정렬하면 최소값, 최대값이 정해져있기 때문에 arr[j+K-1]-arr[j] 하여 MATH.MIN 하면 된다..

D3 치고는 쉬운편이였던 거 같다.