[백준] 2548번 대표 자연수 문제! (silver 3

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        ArrayList<Integer> arr=new ArrayList<>();
        int n=Integer.parseInt(br.readLine());
        int[] accu=new int[n];
        StringTokenizer st=new StringTokenizer(br.readLine());
        int sum=0;
        for(int i=0; i<n; i++){
            int num=Integer.parseInt(st.nextToken());
            sum+=num;
            arr.add(num);
        }
        Collections.sort(arr);
        int min=sum-arr.get(0)*n;
        int answer=arr.get(0);
        accu[0]=answer;
        for(int i=1; i<n; i++){
            int temp=0;
            temp=sum-accu[i-1]-arr.get(i)*(n-i);
            temp+=Math.abs(accu[i-1]-arr.get(i)*(i));
            accu[i]=accu[i-1]+arr.get(i);
            if(temp<min){
                min=temp;
                answer=arr.get(i);
            }
        }
        bw.write(answer+"");
        bw.flush();



    }
}