[백준]2108 - 통계학 - JAVA[자바]

 

---

[접근방법]

 

Counting 정렬(카운팅 정렬) 을 이용하려 한다. ( O(N) )

정렬을 쉽게 하기위해 Arrays.sort(배열) 을 이용할 수 있지만,

3번째의 최빈값을 구할때 "두 번째로 작은 값" 을 출력해야 하므로 복잡하다.

 

Arrays.sort를 사용시 ( O(NlogN) )

중앙값 : (N+1) 위치

범위: (N-1) 번째 인덱스 값  - 0번째 인덱스 값의 차

최빈값 : 배열 첫 번째부터 탐색. 각 값별 최빈값을 count하면서 가장 큰 빈도수 중, 두 번째로 작은 값 찾아내야함

=> 플래그(flag) 변수를 하나 두고, 빈도수가 같았던 적이 있는지 여부를 판별해야 한다. 

 

 

 

최빈값 : 이전의 최빈값의 최댓값보다 현재 최빈값이 더 클 경우 즉, 처음으로 나타난 최빈값일 경우 해당 index(i)를 최빈값에 초기화 해주며, flag를 true로 변경한다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        //입력값의 범위: -4000~4000
        int[] arr = new int[8001];
        
        /*
        * sum = 총 합계
        * max = 최댓값
        * min = 최솟값
        * median = 중앙값
        * freq = 최빈값
        */
        int sum = 0;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        // median과 freq는 -4000~4000을 제외한 수로 초기화하면 된다.
        int median = 100000;
        int freq = 100000;
        
        for(int i = 0; i<N; i++){
            int value = Integer.parseInt(br.readLine());
            sum += value;
            arr[value+4000]++;
            
            if(max < value){
                max = value;
            }
            if(min > value){
                min = value;
            }
        }
        
        
        //순회
        
        int count = 0; //중앙값 빈도 누적 수
        int freq_max = 0; // 최빈값의 최댓값
        
        //이전의 동일한 최빈값이 1번만 등장했을 경우 true; 아닐경우 false
        boolean flag = false;
        
        for(int i = min + 4000; i <= max + 4000; i++){
            
            if(arr[i]>0){
                
                /*
                * 중앙값 찾기
                * 누적 횟수가 전체 길이의 절반에 못 미친다면
                */
                if(count < (N+1) /2){
                    count += arr[i];   // i 값의 빈도수를 count 에 누적
                    median = i - 4000;
                }
                
                /*
                * 최빈값 찾기
                * 이전 최빈값보다 현재 값의 빈도수가 더 높을 경우 
                */
                if(freq_max < arr[i]){
                    freq_max = arr[i];
                    freq = i - 4000;
                    flag = true; //첫 등장이니까 true로 변경
                }
                
                // 이전 최빈값 최댓값과 동일한 경우면서 한 번만 중복되는 경우
                else if(freq_max == arr[i] && flag == true){
                    freq = i - 4000;
                    flag = false;
                }
            }
        }
        System.out.println((int)Math.round((double)sum/N));
        System.out.println(median);
        System.out.println(freq);
        System.out.println(max-min);
            
    }
}

동일한 최빈값을 갖는다면 두 가지 경우의 수가 생긴다.

1. 동일한 최빈 값이 이전에 1번만 나타났을 경우 -> flag가 true이다. 두번째로 작은 값이 현재 i가 되고, 결과적으로 freq(최빈값 변수)를 초기화 해주면 된다. 그리고 flag를 false로 바꾸어준다:

2. 동일한 최빈값이 이전에 2번 이상 타났을 경우 -> flag가 false 이다. 이후에 같은 최빈값이 나오더라도 이미 두 번째로 작은 값은 변하지 않기 때문에 flag를 false상태로 두어 else if 문을 실행시키지 않으며 두 번째로 작은 최빈값이 수정되지 않는다. 

 

산술평균 : 그냥 나누면 int형 떄문에 나눗셈 과정에서 소수점이 무조건 버려지게 된다.
반올림을 위해 Math.round를 쓰기 전에 이미 나눗셈에서 오차가 날 수 있다

=> sum 이나 N 중 하나를 double로 캐스팅하여 소수점이 버려지는 것을 방지하고, 반올림해서 다시 int형으로 캐스팅해야한다.