[코드트리] 최대 최소간의 차

문제링크

문제

n개의 수가 주어지는데, 이 값들에서 최대 - 최소가 k이하가 되야한다
수가 변경되면 변경된 값의 차이의 절대 값만큼(|a - b|) 비용이 들때
이를 만족하는 경우를 만드는 최소 비용은?

틀렸던 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] lst = new int[n];

        for (int i = 0; i < n; i++)
            lst[i] = sc.nextInt();

        Arrays.sort(lst);

        int res = 0;
        int diff = (lst[n - 1] - lst[0]) - k;
        while (diff > 0){
            if (diff % 2 == 0){
                lst[0] += diff / 2;
                lst[n - 1] -= diff / 2;
                res += diff;
            }
            else{
                lst[0] += diff / 2 + 1;
                lst[n - 1] -= diff / 2;
                res += diff;
            }
            Arrays.sort(lst);
            diff = (lst[n - 1] - lst[0]) - k;
        }
        System.out.print(res);

    }
}     

틀렸던 이유

• 범위 내의 차를 만들기 위해 최대 최소의 차이를 구해서 이를 더해주거나 빼줌
  => 필요 없는데 값이 변경되는 경우가 생김
• 차이가 홀수인 경우 작은 값에 더 더해주었는데 이게 올바른 결과가 아닐 수 있음

답안

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] lst = new int[n];

        for (int i = 0; i < n; i++)
            lst[i] = sc.nextInt();

        Arrays.sort(lst);
        int min = lst[0];
        int max = lst[n - 1];

        int res = Integer.MAX_VALUE;

        for (int i = min; i <= max; i++){
            int tmp = 0;
            for (int j = 0; j < n; j++){
                if (lst[j] >= i && lst[j] <= i + k)
                    continue;
                tmp += Math.min(Math.abs(lst[j] - i), Math.abs(lst[j] - i - k));
            }
            res = Math.min(tmp, res);
        }
        
        System.out.print(res);

    }
}

• 범위가 지정되어 있으니 (차이가 k이므로 [a, a +k])
  a 에 해당되는 최소값을 입력값의 최소, 최대값을 입력값의 최대로 정해
  그 사이에 해당하는 값을 a로 정하여 모든 경우의 수에서 최소 값을 구함