문제
N개의 자연수가 주어질 때, 모든 수와의 차이의 절댓값의 합이 최소인 대표 자연수를 구하라. 여러 개이면 가장 작은 수를 출력한다.
입력
첫째 줄에 N, 둘째 줄에 N개의 자연수가 주어진다 (1 이상 10,000 이하).
출력
대표 자연수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 1 2 3 4 5 | 3 |
풀이
카운팅 배열과 누적합을 이용하여 각 값을 대표로 선택했을 때의 비용을 O(1)에 계산한다.
- 값 범위(1~10000)의 카운팅 배열에 각 수의 등장 횟수와 값 합을 기록한다
- 누적합으로
sum[i](i 이하 값의 합)와cnt[i](i 이하 개수)를 구한다 - 각 값 i에 대해 좌측 비용
i*cnt[i-1] - sum[i-1]과 우측 비용(sum[MAX] - sum[i]) - i*(cnt[MAX] - cnt[i])를 합산한다 - 최소 비용인 가장 작은 값을 출력한다
핵심 아이디어: 절댓값 합의 최솟값은 중앙값에서 달성되며, 누적합으로 각 후보의 비용을 O(1)에 계산한다.
코드
package day749;
import java.io.*;
import java.util.*;
public class Day710BOJ2548대표자연수 {
private static final int LIMIT = 10000;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] sum = new int[LIMIT + 1];
int[] cnt = new int[LIMIT + 1];
for (int i = 1; i <= n; i++) {
int cur = Integer.parseInt(st.nextToken());
sum[cur] += cur;
cnt[cur]++;
}
for (int i = 1; i <= LIMIT; i++) {
sum[i] += sum[i - 1];
cnt[i] += cnt[i - 1];
}
int min = Integer.MAX_VALUE;
int ans = 0;
for (int i = 1; i <= LIMIT; i++) {
if (cnt[i] - cnt[i - 1] == 0)
continue;
int calc = (i * cnt[i - 1] - sum[i - 1]) + (sum[LIMIT] - sum[i] - i * (cnt[LIMIT] - cnt[i]));
if (min > calc) {
min = calc;
ans = i;
}
}
System.out.println(ans);
}
}복잡도
- 시간: O(N + M) - M은 값 범위(10000)
- 공간: O(M)