[백준] S3 2548번 대표 자연수 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

2548번: 대표 자연수

[문제] 

정보초등학교의 연아는 여러 개의 자연수가 주어졌을 때, 이를 대표할 수 있는 대표 자연수에 대하여 연구하였다. 그 결과 어떤 자연수가 다음과 같은 성질을 가지면 대표 자연수로 적당할 것이라고 판단하였다.

“대표 자연수는 주어진 모든 자연수들에 대하여 그 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수이다.”

예를 들어 주어진 자연수들이 [4, 3, 2, 2, 9, 10]이라 하자. 이때 대표 자연수는 3 혹은 4가 된다. 왜냐하면 (4와 3의 차이) + (3과 3의 차이) + (2와 3의 차이) + (2와 3의 차이) + (9와 3의 차이) + (10과 3의 차이) = 1+0+1+1+6+7 = 16이고, (4와 4의 차이) + (3과 4의 차이) + (2와 4의 차이) + (2와 4의 차이) + (9와 4의 차이) + (10과 4의 차이) = 0+1+2+2+5+6 = 16으로 같으며, 이 두 경우가 차이들의 합을 최소로 하기 때문이다. 비교를 위하여 평균값인 5의 경우를 생각하여 보면, (4와 5의 차이) + (3과 5의 차이) + (2와 5의 차이) + (2와 5의 차이) + (9와 5의 차이) + (10과 5의 차이) = 1+2+3+3+4+5 = 18로 위의 두 경우보다 차이들의 합이 더 커짐을 볼 수 있다.

연아를 도와서 위의 성질을 만족하는 대표 자연수를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다.

[출력]

첫째 줄에 대표 자연수를 출력한다. 대표 자연수가 두 개 이상일 경우 그 중 제일 작은 것을 출력한다.

 

 

---

[풀이]

1. 입력받은 수들을 정렬해준다. (대표 자연수가 두 개 이상이라면 작은 것을 출력하므로 오름차순 선택)

2. 처음 값부터 마지막 값까지 각 자리의 값들과의 차들의 합을 구해 비교하며 작은 것으로 갱신해준다.

3. 결과를 출력한다.

[접근]

1. 입력받은 수들을 정렬하고 각 수를 비교하면서 그 차이를 더해 가장 작은 것을 출력하면 되겠다고 생각하였고 그렇게 문제를 해결하였다.

[코드]

package BOJ_silver;

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

public class Main_S3_2548 {
	static int n;
	static int arr[];
	static int min;
	static int min_sum = Integer.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// 오른차순 정렬
		Arrays.sort(arr);
		
		// 브루트포스
		for (int i = 0; i < n; i++) {
			int sum = 0; // 각 순서에 차이합
			
			for (int j = 0; j < n; j++) {
				sum += Math.abs(arr[i] - arr[j]); // 차이합을 더하기
				
				// 만약 최소보다 값이 커진다면 탈출
				if (sum > min_sum)
					break;
				// 만약 for문을 다 돌았다면
				if (j == n - 1) {
					// 만약 sum이 최소합보다 작다면 갱신
					if (sum < min_sum) {
						min_sum = sum;
						min = arr[i];
					}
				}
			}
		}
		
		// 결과 출력
		System.out.println(min);
	}
}