[Java] BOJ 2108 통계학

문제 

문제 링크 https://www.acmicpc.net/problem/2108

• 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.
  1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
  2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
  3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
  4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이
• N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.
• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다.
• 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
• 첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.
• 둘째 줄에는 중앙값을 출력한다.
• 셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
• 넷째 줄에는 범위를 출력한다.

아이디어

• 절댓값 4000이 범위라고 했으므로 배열을 8001크기로 만들어서 입력받는 숫자에 4000을 더한 위치에 +1을 했다.
• 입력받으면서 최솟값과 최댓값을 갱신해줬고, 산술평균을 구하기 위한 총합도 계산했다. 
• 입력을 다 받은 후, 배열 크기만큼 반복문을 돌리면서 해당 배열의 값이 1이상이면 카운트 변수에 +1을 해주고 해당 카운트가 (전체 입력받은 개수 / 2) + 1인지 확인하며 중앙값을 찾았다. 
• 그리고 배열 값에 따라 해당 배열값이 최빈값이 될 수 있는 수보다 더 크다면 해당 배열 위치에 해당하는 숫자가 최빈 값이므로 최빈값을 갱신해줬다.
• 만약 최빈값이 여러개일 경우, 두번째로 작은 수를 출력해야되므로 boolean 변수를 통해 만약 최빈값의 개수와 해당 변수의 개수가 똑같고 boolean 변수가 false이면 두번째 작은 최빈값이므로 최빈값을 갱신해주고 boolean값을 true로 변환해준다.

겪은 시행착오

• 많은 시행착오를 겪었다... 우선 많이도 틀렸다... 분명 예제는 다 맞고 다른 반례들도 다 맞는데 자꾸 틀렸다고 나왔다...
• 반례를 찾고 또 찾은 결과 최빈값을 계산하는 과정에서 문제가 있음이 드러났다...
• 최빈값이 여러개일때, 두번째로 작은 최빈값을 구하기 위해 boolean 변수를 사용하는데, 만약 최빈값이 갱신된다면(최빈값이 여러개가 되는 경우 X, 개수가 더 많아서 새롭게 갱신될때) boolean 변수도 다시 false로 초기화해줘야됐는데 그 초기화를 해주지 않아서 틀렸었다....(분발하자...)

'틀렸습니다'의 축제....

반례 찾느라 너무너무 힘들었다....ㅜㅜㅜㅜㅜㅜ

코드

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

public class BOJ2108 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력받는 숫자의 개수
        int N = Integer.parseInt(br.readLine());

        // 평균 계산할 변수
        double avg = 0;

        // 최댓값, 최솟값 계산을 위한 변수
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        // 중앙값을 찾을 때 쓰는 변수
        int mid = 0;

        // 최빈값을 찾을 때 쓰는 변수
        int value = 0;

        // 최빈값을 찾기 위한 배열
        int arr[] = new int[8001];

        // 산술평균 결과값
        int result1 = 0;
        // 중앙값 결과값
        int result2 = 0;
        // 최빈값 결과값
        int result3 = 0;
        // 범위 결과값
        int result4 = 0;

        for(int i = 0; i < N; i++){
            int n = Integer.parseInt(br.readLine());

            // 평균 값을 계산하기 위해 더해줌
            avg = avg + n;

            // 배열의 해당 값 위치에 + 1
            // 절댓값 4000이라고 했으므로 마이너스도 올 수 있으니 +4000을 해줌
            arr[n + 4000] = arr[n + 4000] + 1;

            // 입력들어오는 값이 현재 최솟값보다 작다면 갱신
            if(min > n){
                min = n;
            }

            // 입력들어오는 값이 현재 최댓값보다 크다면 갱신
            if(max < n){
                max = n;
            }
        }

        // 몇개째인지 세기위한 변수
        int cnt = 0;

        // 최빈값이 같을 경우, 제일 작은 수인지 판별하기 위해서
        boolean TF = false;

        // 중앙값과 최빈값을 찾기 위한 반복문
        for(int i = 0; i < 8001; i++){
            // 만약 1보다 크다면 입력이 됐었다는 의미므로
            // 입력된 횟수만큼 카운트
            if(arr[i] >= 1){
                // 입력된 횟수만큼 반복문을 돌면서
                for(int j = 0; j < arr[i]; j++){
                    // 1씩 카운트에 더해주고
                    cnt = cnt + 1;

                    // 만약 카운트가 전체 개수를 2로 나눈것에서 1을 더한 값과
                    // 같다면 중앙값이므로 중앙값 갱신
                    // 처음 저장할때 마이너스를 고려해서 + 4000을 해줬으므로 -4000을 해줌
                    if(cnt == ((N / 2) + 1)){
                        mid = i - 4000;
                    }
                }

                // 만약 기존 최빈값의 개수보다 더 개수가 크다면
                if(value < arr[i]){
                    // 최빈값의 개수를 갱신하고
                    value = arr[i];

                    // 해당하는 최빈값을 결과값에 저장
                    result3 = i - 4000;

                    // 최빈값이 갱신됐으므로
                    // TF를 다시 초기화
                    // 최빈값이 될 수 있는 개수를 가진 수 중 다시 가장 작은 수가 됐으므로
                    TF = false;
                }
                // 만약 기존 최빈값의 개수와 개수가 같다면
                else if(value == arr[i]){
                    // 여러개의 최빈값들 중 최솟값인지 판단해야함
                    // 만약 변수가 false라면 아직 첫번째 값이라는 의미므로
                    // 현재 값이 두번째로 작은 수가 됨 따라서 TF를 true로 바꾸고
                    // 최빈값 갱신
                    if(!TF){
                        // 해당하는 최빈값을 결과값에 저장
                        result3 = i - 4000;

                        TF = true;
                    }
                }
            }

            // 입력된 횟수만큼 모든 숫자를 찾았으면 반복문 종료
            if(cnt == N){
                break;
            }
        }

        result1 = (int)Math.round(avg / N);
        result2 = mid;
        result4 = max - min;

        System.out.println(result1);
        System.out.println(result2);
        System.out.println(result3);
        System.out.println(result4);
    }
}