[02108] 통계학

[02108] 통계학

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

산술평균 : N개의 수들의 합을 N으로 나눈 값
중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
최빈값 : N개의 수들 중 가장 많이 나타나는 값
범위 : N개의 수들 중 최댓값과 최솟값의 차이
N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

코드

#include <iostream>

using namespace std;

int main() {
    int N, count[8001] = {0, }, sum = 0;

    scanf("%d", &N);

	// 입력 받을 때 마다 count
    for(int tmp, i = 0; i < N; i++) {
        scanf("%d", &tmp);
        sum += tmp;
        count[tmp + 4000]++;
    }

    // 산술평균
    printf("%.0lf\n", (double)sum/N);

    // 중앙값
    for(int acc = 0, i = 0; i < 8001; i++) {
        acc += count[i];
        if(acc > N/2) {
            printf("%d\n", i - 4000);
            break;
        }
    }

    // 최빈값
    int mode, max = 8000;
    for(int i = 8001; i-- > 0;) {
        if(count[max] < count[i]) {
            mode = i;
            max = i;
        } else if(count[max] == count[i]) {
            mode = max;
            max = i;
        }
    }
    printf("%d\n", mode - 4000);

    // 범위
    for(int i = 8001; i-- > 0;) {
        if(count[i] > 0) {
            max = i;
            break;
        }
    }
    for(int i = 0; i < 8001; i++) {
        if(count[i] > 0) {
            printf("%d\n", max - i);
            break;
        }
    }
}

부가 설명

이 문제는 애초에 count sort를 활용해 풀어야 하는 문제인 것 처럼 count sort를 사용해 쉽게 풀 수 있었다.
count[8001]은 -4000 부터 4000까지의 숫자를 4000의 offset을 가진 배열로 나타내 해당 index가 나타내는 숫자의 개수를 갖는 배열이다.

• 산술평균(mean)
  평균은 오버헤드를 줄이기 위해 입력받을 때 마다 sum에 누적합으로 더한 후 double형으로 N으로 나눠주고 %.0lf로 반올림하여 출력해주었다.
• 중앙값(median)
  중앙값은 count한 값들에 대해 누적값을 구할 때 N/2이상이 되는 순간의 숫자가 중앙값이 된다.
• 최빈값(mode)
  최빈값은 조금 이상했는데, 최빈값이 두개 이상일 경우 두번째로 작은 숫자여야 한다는 조건때문에 8000부터 시작해 내려오면서 확인했다.
  count[]가 빈도를 나타내는 배열이므로 count[]의 최댓값을 구해가면서, 같은 숫자가 나오면 mode를 업데이트 하고, 더 큰 숫자가 나오면 mode와 max 둘 다 업데이트 하면서 최빈값이 하나일 때와 두개 이상일 때를 동시에 고려했다.
• 범위(range)
  범위는 아주 간단했다. count[]에는 -4000부터 4000까지 순서대로의 개수를 나타내므로 1개 이상 나온 수들 중 가장 작은 index와 큰 index의 차이가 범위이다.

출처 : https://www.acmicpc.net/problem/2108