문제 번호 2108번 : 통계학 - JAVA [자바]

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

2108번: 통계학

문제 설명

 

입력된 값의 산술평균, 중앙값, 최빈값, 범위를 출력하는 문제입니다.

 

보고 오기를 추천하는 게시물

https://kkungchan.tistory.com/293

자바로 구현한 카운팅 정렬(Counting Sort/계수 정렬) 알고리즘

 

문제 풀이

해당 문제는 카운팅 정렬을 사용해 문제를 풀 것입니다. 카운팅 정렬은 위에 게시물에 설명되어 있으니 보고 오는 것을 추천드립니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        double add = 0; //산술 평균을 구하기 위한 누적 값(소수점을 계산해야 함으로 double 형으로 선언)

        int mode = 0; //최빈값
        int modeCheck = 0;//최빈값을 찾기 위한 값
        boolean modeFlag = false;//최빈값을 찾기 위한 flag

        int midNum = 0; //중앙값

        int first = 0;//범위를 위한 첫번째 값
        int last = 0;//범위를 위한 마지막 값

        int midCheck = 0;//중앙값과 first,last을 구하기 위한 값

        int n = sc.nextInt();//n 입력

        //-4000~4000까지 수를 모두 나타내기위해 8001개의 배열을 만듬
        int[] array = new int[8001];

        //카운팅 정렬
        for(int i=0; i<n; i++){
            array[sc.nextInt()+4000]++;
        }


        for(int i=0; i<array.length; i++){
            //최빈값 구하기
            /*
            최빈값이 여러개일때 두번째 값을 구하는 방식
                최빈값이 여러개일 때 두번째로 작은 값을 출력하라는 것은
                두번째 최빈값을 구하라는 말과 같다.
                그렇다면 해당 값의 빈도수가 같은 값이 존재하고 아
                래 조건문이 실행되지 않았을 때
                두번째 i-4000이 두번째 최빈값이라는 것을 알 수 있고
                세번째 부터는 실행되지 않도록 flag를 false로 만들어준다.
             */
            if(modeFlag == true && modeCheck == array[i]){
                mode = i-4000;
                modeFlag = false;
            }
            /*
            최빈값이 한개일때 구하는 방식
                카운팅 정렬의 max값을 구한는 방식과 같다고 보면 된다.
                배열을 차례대로 진행하면서 0보다 큰 값이 차례대로 나오면
                modeCheck값을 순차적으로 늘려준다.
                그리고 가장 큰 수가 나오면 더이상 modeCheck는 늘어나지 않고
                그 때의 i-4000이 가장 빈도수가 높은 수가 된다.
             */
            if(modeCheck < array[i]){
                modeCheck = array[i];
                mode = i-4000;
                modeFlag = true;
            }

            /*
            * 산술 평균 : add을 계속 누적한 후 출력할 떄 Math.round을 사용해서 소수점을 반올림 해준다.
            * 중앙 값 : 카운팅 정렬로 모두 정렬이 되어 있을 때 midCheck을와 n값을 사용하여 중앙 값을 구해 출력한다.
            * 범위 midCheck을 사용에 첫번째 값과 마지막 값을 구하여 구한다.
            */
            while(array[i]-->0){
                add = add + (i-4000);
                midCheck++;
                if(midCheck == (n/2+1)){
                    midNum = i-4000;
                }
                if(midCheck == 1){
                    first = i-4000;
                }
                if(midCheck == n){
                    last = i-4000;
                }
            }

        }

        //결과 출력
        System.out.println(Math.round(add/n));
        System.out.println(midNum);
        System.out.println(mode);
        System.out.println(last - first);
    }
}

 

카운팅 정렬을 이해했다면 전체적인 흐름은 어렵지 않을 것입니다. while문을 돌리면서 해당 인덱스로 산술 평균과 중앙값, 범위를 구할 수 있습니다.

최빈값을 고민을 많이했는데 간단히 생각해서 배열의 max값을 구하는 방법을 생각해 구현했습니다. 최댓값을 가지고 있는 인덱스가 최빈값이 되게 됩니다.

여기서 두 번째 고민은 동일한 최빈값이 있을 때는 두 번째로 작은 값이 출력되도록 하는 것입니다. 그러기 위해서는 최빈값이 결정되고 딱 한번 같은 횟수의 원소를 만나면(카운팅 정렬로 인해 배열에 횟수가 저장됨으로) 그 인덱스를 출력해 주면 됩니다. 그러기 위해서는 flag로 해당 조건이 실행되었는지 확인해 주고 인덱스를 변경해 주면 됩니다.