백준 2108 통계학

문제

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

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값

2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

---

코드

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        int n=Integer.parseInt(br.readLine());
        int[] counting=new int[8001];
        int[] array=new int[n];
        int[] sorted=new int[n];
        int sum=0;

        for(int i=0; i<n; i++) {
            array[i] = Integer.parseInt(br.readLine());
            sum += array[i];
        }
        for(int i=0; i<n; i++)
            counting[array[i]+4000]++;

        LinkedList<Integer> list=new LinkedList<>();
        int max=0;
        for(int i=0; i<8001; i++)
            if(counting[i]>0){
                if(list.isEmpty()) {
                    max=counting[i];
                    list.add(i);
                }
                else if(max<counting[i]){
                    max=counting[i];
                    list.clear();
                    list.add(i);
                }
                else if(max==counting[i]){
                    list.add(i);
                }
            }

        for(int i=0;i<8000;i++)
            counting[i+1]+=counting[i];
        for(int i=n-1; i>=0; i--)
            sorted[--counting[array[i]+4000]]=array[i];

        bw.write(Math.round((double) sum/n)+"\n");
        bw.write(sorted[n/2]+"\n");
        if(list.size()>1){
            list.removeFirst();
            bw.write(list.remove()-4000+"\n");
        }
        else
            bw.write(list.remove()-4000+"\n");
        bw.write(sorted[n-1]-sorted[0]+"\n");

        bw.flush();
    }
}

---

해결 과정

1. 우선 산술평균을 구하기 위해서 최초의 배열을 입력 받을 때 sum에 모두 더해줬다. 어쨌든 정렬을 해야 하기 때문에 어떤 정렬을 사용할까 고민하다가 수의 범위가 -4000 ~ 4000 인 것을 보고 어차피 최빈값도 구해야 하기 때문에 Counting Sort를 사용했다. 같은 빈도의 수가 여러 개라면 그 중 두번째를 출력해야 하기 때문에 Linked List를 만들어서 더 높은 빈도의 수가 나올 때마다 list를 clear 해주고 추가해줬다. Linked List를 사용한 이유는 삽입 연산이 매우 빠르기 때문이고, 탐색할 필요가 없어서 채택했다.
2. 😁