문제
수 N개가 주어졌을 때, 산술평균, 중앙값, 최빈값, 범위를 구하는 문제이다. 최빈값이 여러 개일 경우 두 번째로 작은 값을 출력해야 하며, 산술평균은 소수점 이하를 반올림한다.
입력
첫째 줄에 수의 개수 N (1 이상 500,000 이하의 홀수)이 주어진다. 그 다음 N개의 줄에 정수가 한 줄에 하나씩 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
출력
첫째 줄에 산술평균, 둘째 줄에 중앙값, 셋째 줄에 최빈값, 넷째 줄에 범위를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 1 3 8 -2 2 | -1 1 1 10 |
풀이
정렬 대신 카운팅 배열을 이용해 통계 값 4가지를 한 번의 순회로 모두 구하는 방식으로 해결한다. 입력값 범위가 -4000 ~ 4000으로 제한되어 있어 크기 8001의 배열에 빈도를 기록한다.
- N개의 정수를 읽으면서 빈도 배열(
cnt[])에 누적하고, 동시에 합계·최댓값·최솟값을 갱신한다. - 빈도 배열을 최솟값부터 최댓값까지 순회하여 중앙값을 찾는다: 등장 횟수 누적이
(N+1)/2이상이 되는 첫 번째 값이 중앙값이다. - 최빈값을 추적할 때 같은 빈도의 두 번째 값이 필요하므로
flag로 상태를 관리한다. - 산술평균은 정수 나눗셈 대신
double로 계산 후%.0f로 반올림 출력한다. - 범위는
max - min으로 출력한다.
핵심 아이디어: 정렬 없이 카운팅 배열로 O(N + R) (R = 값의 범위)에 중앙값과 최빈값을 동시에 구한다. 최빈값 처리 시 동일 빈도가 두 번 이상 나올 경우 두 번째 값을 출력해야 함에 주의한다.
코드
package com.ssafy.an.day049;
import java.util.Scanner;
public class Day06BOJ2108통계학 { // 2108
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.nextLine());
int[] cnt = new int[8001];
int sum = 0;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int cntMaxValue = Integer.MIN_VALUE;
int mid = Integer.MIN_VALUE;
for (int n = 0; n < N; n++) {
int num = Integer.parseInt(sc.nextLine());
cnt[num + 4000]++;
sum += num;
if (max < num)
max = num;
if (min > num)
min = num;
}
int cntMid = 0;
int cntMax = 0;
boolean flag = false;
for (int i = min + 4000; i <= max + 4000; i++) {
if (cnt[i] > 0) {
if (cntMid < (N + 1) / 2) {
cntMid += cnt[i];
mid = i - 4000;
}
if (cntMaxValue < cnt[i]) {
cntMaxValue = cnt[i];
cntMax = i - 4000;
flag = true;
} else if (cntMaxValue == cnt[i] && flag == true) {
cntMax = i - 4000;
flag = false;
}
}
}
System.out.printf("%.0f\n", (double) sum / N);
System.out.printf("%d\n", mid);
System.out.printf("%d\n", cntMax);
System.out.printf("%d\n", max - min);
sc.close();
}
}복잡도
- 시간: O(N + R) — N은 입력 수, R은 값의 범위(8001). 정렬 없이 선형 순회로 해결
- 공간: O(R) — 카운팅 배열 크기 8001