(SWEA) 20728. 공평한 분배 2 [D3] Java

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

[문제 설명]

사탕이 담긴 N개의 주머니가 있다. 이 중 i (1≤i≤N) 번째 주머니에는 사탕이 ai개 들어 있다. 당신은 이 주머니 중 정확히 K개를 선택하여 어린이들에게 나누어 주려고 한다.
공정성을 위해, 당신은 나눠 준 주머니 가운데 사탕의 개수가 가장 많은 것과 가장 적은 것의 사탕 개수 차이를 최소화하려고 한다.
모든 유효한 방법 중 차이의 최솟값을 구하는 프로그램을 작성하라.
 

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 두 개의 줄로 이루어진다. 첫 번째 줄에는 주머니의 개수 N (2≤N≤50)과 나눠 줄 주머니의 개수 K (2≤K≤N)이 공백 하나를 사이로 두고 주어진다.
두 번째 줄에는 주머니 속 사탕의 개수를 나타내는 N개의 정수 a1,a2, ⋯ ,aN(1≤ai≤109)이 공백 하나씩을 사이로 두고 주어진다.
 

[출력]

각 테스트 케이스마다, 차이의 최솟값을 출력한다.

 

입력예제

3 3 2 1 2 3 3 3 5 20 10 4 3 4 3 2 1

 

출력예제

#1 1  #2 15 #3 2

첫 번째 예제: 주머니 2개를 고르는 방법은 {1, 2}, {1, 3}, {2, 3}이 있다. 각각의 (최대) – (최소) 값은 1, 2, 1이다. 이 중 최솟값은 1이다.
두 번째 예제: 무조건 모든 주머니를 나눠줘야 한다.
 

 

 

[풀이]

 

첫번째 테스트케이스를 보면N = 3, K = 2사탕 바구니에 사탕은 각각 1 2 3 이 담겨 있습니다.

 

나올 수 있는 경우의 수는 {1,2}, {1,3}, {2,3} 이다. 여기서 사탕이 가장 많은 것 - 적은 것의 최솟값은 {1,2} 와 {2,3} 때문에 1이라는 최솟값이 나옵니다.

 

여기서 잘 생각해보면 정렬이 되어있다는 가정하 {1,3} 처럼 서로 붙어 있는 값이 아니라 떨어져 있는 값은 절대 최솟값이 나올 수가 없습니다.

 

왜냐하면, {1,2} 나 {2,3} 처럼 붙어 있어야만 최솟값이 나올 수 있기 때문입니다.

 

만약 N = 5, K = 3 이고 사탕 바구니에 사탕이 각각 1 100 101 102 200 이 담겨있다고 한다면

예시

여기서 최솟값이 나올 수 있는 경우의 수는 {1, 100 ,101}, {100, 101, 102}, {101,102, 200} 인 경우 뿐.

 

1이라는 값이 포함되어 있을 때 아까처럼 붙어 있는 값이 아니라 떨어져 있는 값이 한 묶음이라면 나머지 2개의 값은 1에서 멀어지면 안됩니다.

 

즉, 1바로 다음값인 100 그리고 101이 들어와야 이 사탕이 가장 많은 것 - 가장 적은 것을 했을 때 최솟값이 될수 있습니다.

ex) {1,100,200}, {1, 101,102}의 최솟값은 각각 200-1 = 199,  102-1 = 101로 {1,100,101}의 101 - 1 = 100보다 큼

 

따라서 코딩을 할 때, 이 규칙성으로 반복문을 만들어야 합니다.저 문제에서의 답은 딱 봐도 {100, 101, 102} 로 102-100 인 2가 답입니다.

 

알고리즘 예시

 

N = 5, K = 3

1 100 101 102 200

for문으로 3개를 1묶음씩 3번 반복하면 값을 알 수 있습니다.

 

1. {1, 100, 101} 경우, 최솟값 = 100

2. {100, 101, 102} 경우, 최솟값 = 2

3. {101, 102, 200} 경우, 최솟값 = 99

 

따라서 100, 2, 99 중 가장작은 값인 2가 정답

 

밑에는 Java코드로 구현했습니다. 

 

[Java code]

import java.util.Arrays;
import java.util.Scanner;
import java.io.FileInputStream;

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

        for (int tc = 1; tc <= T; tc++) {

            int N = sc.nextInt();
            int K = sc.nextInt();
            long[] arr = new long[N];
            for (int i=0; i<N; i++) arr[i] = sc.nextInt();
            Arrays.sort(arr);//정렬
            long result = 1000000000, max = 0, min = 0;
            //result에는 사탕의 개수의 최대값인 10의 9승을 넣어주었다.
            for (int i=0; i<=N-K; i++){
                min = arr[i];//최솟값
                max = arr[K-1+i];//최댓값
                result = Math.min(max - min, result);
            }
            StringBuilder sb = new StringBuilder();
            sb.append("#" + tc + " ");
            sb.append(result);
            System.out.println(sb);

         
        }
    }
}

 

 

 

코딩테스트 문제 풀이 설명을 처음 해보는 거라 엉망진창으로 설명한 거 같지만 이 문제가 이해가 안 되는  분들에게 도움이 되면 좋겠습니다.