[백준] 2548 대표 자연수 - 정렬(Sorting) + 수학(Math) JAVA

https://www.acmicpc.net/problem/2548

코드설명

정렬(Sorting) 문제입니다.

 

처음 문제를 보면, 문제에 평균값인 5의 경우를 생각해보면.... 이라면서 평균에 대한 이야기를 합니다.

이러한 문구를 보고, 대표 자연수는 당연히 모든 수와 가장 가까운, 차이가 적은 수는 평균값임을 알 수 있습니다.

 

하지만, 여기서 평균값인 5가 대표자연수가 아닌 이유는 4는 4를 뺼 수 있으므로 더 가까워질 수 있기 떄문입니다.

그래서 처음에 평균값을 구하고(여기서는 5), 5와 가장 가까운 값의 Index를 BinarySearch로 찾은뒤 해당 인덱스에서 양 옆의 Index를 비교하여 가장 5와 가까운 값을 반환하도록 처리하는 것을 생각했습니다.

 

두번쨰 방법으로는, Arrays.sort를 통해 arr을 오름차순으로 정렬하고, 정렬된 배열의 중앙값을 찾으면 됩니다.

N이 홀수일경우 정확히 중앙에 있는 값이 중앙값이고, 

N이 짝수일 경우, 중앙에 있는 두 값중 작은 값이 중앙값이 됩니다. 

그러므로 (N - 1) / 2를 통해 모두 만족할 수 있습니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int N, T, M;
    private static int answer = 0;
    private static int[] arr;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		//평균값을 구하고, 그 값과 가장 가까운값.
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		
		int mid = (N - 1) / 2;
		System.out.println(arr[ mid ] );
	}
    
}