[BOJ] 백준 2108 통계학

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

계수 정렬(Counting Sort)  

계수 정렬(Counting Sort)

N개의 수들에 대한 기본 통계값을 구하는 문제입니다. (N은 홀수라고 가정.)

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

② 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값

③ 최빈값 : N개의 수들 중 가장 많이 나타나는 값

④ 범위 : N개의 수들 중 최댓값과 최솟값의 차이

 

※ 1 ≤ N ≤ 500,000이며, 입력되는 정수는 -4000 ≤ X ≤ 4000

첫번째 산술 평균의 경우 소수점 이하 첫째 자리에서 반올림한 값.

세번째 최반값이 여러개인 경우 두 번째로 작은 값을 출력.

 

중앙값

아래와 같이 수를 나열 했을 때, 중앙에 위치한 수

2 2 2 2 2 3 → 중앙값 = 『2』

 

▶ 범위

최솟값, 최대값을 찾아야 합니다. ← 정렬

* 선택, 삽입, 퀵 정렬을 이용하지 않고 배열 이용. 

-4000 ≤ X ≤ 4000 범위를 아래와 같이 0 ≤ index ≤ 8000

ex. 『0』을 인덱스 『4000』으로 처리

ex. 『-4000』을  인덱스 『0』으로 처리

ex. 『4000』을  인덱스 『8000』으로 처리

 

▶ 배열의 원소에는 해당 숫자가 나타난 횟수 저장.

ex. 『5』가 두 번 입력되었다면 arr[4005] = 2.

---

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
                 
        int[] arr = new int[8001];
         
        for(int i=0; i<N; i++) {
            int idx = Integer.parseInt(sc.next());
            // 음수를 고려해서 인덱스를 조작한다.
            arr[idx+4000]++;
        }
         
        int sum = 0; // 합계
        int midValue = 0; // 중앙값
        int count = 0; // 중앙에 위치한 숫자를 알기 위함
        int Frequent_value = 0; // 빈번정도를 측정하기 위함
        int min = 4001; // 최솟값
        int max = -4001; // 최대값
         
        for(int i=0; i<=8000; i++) {
            // 한 번이라도 입력받았다면 합한다.
            if(arr[i] > 0) {
                // 해당 숫자가 중첩해서 나온 만큼
                int realVal = i - 4000;
                sum += arr[i] * realVal;
                 
                // 해당 숫자가 중복된 만큼 count++
                for(int j=0; j<arr[i]; j++) {
                    count++;
                    if(count == N / 2 + 1) {
                        midValue = realVal;
                    }    
                }
                 
                // 최소값을 탐색
                if(min > realVal) {
                    min = realVal;
                }
                // 최대값을 탐색
                if(max < i-4000) {
                    max = realVal;
                }
            }
            // 가장 많이 나타난 횟수를 측정
            if(Frequent_value < arr[i]) {
                Frequent_value = arr[i];
            }
             
        }
        /*
        1.산술평균을 출력한다. (소수점 이하 첫째 자리에서 반올림한 값을 출력한다.)
        2.둘째 줄에는 중앙값을 출력한다.
        3.셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
        4.넷째 줄에는 범위를 출력한다. (최댓값과 최솟값의 차이)
        */
        System.out.println(Math.round((float) sum / N));
        System.out.println(midValue);
        // 가장 많이 나타난 횟수에 해당하는 숫자들을 작은 값에서부터 탐색
        List<Integer> FrequentValueList = new LinkedList<>();
        for(int i=0; i<=8000; i++) {
            if(Frequent_value == arr[i]) {
                FrequentValueList.add(i - 4000);
                // 두개 이상 들어가면 더이상 찾을필요 없으므로 종료
                if(FrequentValueList.size() >=2) {
                    break;
                }
            }
        }
        // 최빈값이 오직 한개이면 list.get(0)이고 2개이면 list.get(1)의 형태가 되도록 코딩
        System.out.println(FrequentValueList.get(FrequentValueList.size()-1));
        // 범위는 |최대값-최소값|
        System.out.println(Math.abs(max - min));
    }
}