[java] 백준 알고리즘 2108번 통계학 풀이

이 문제가 어려운 건

최빈값 때문이다.

최빈값이 여러개면 두번째 작은 값을 출력하라니...

최빈값을 모아놓고 거기서 또 크기 비교를 해야한다는 것이다.

나머지는 금방 구현했지만, 최빈값을 어떻게 처리할지 고민하는데 시간을 많이 보냈다.

일단 입력할 때부터

양수와 음수를 구분해서 배열을 만들었다.

이때 양수와 음수 배열에 입력값을 순서대로 넣는 것(배열 순서 0번째부터 ~배열의 최대 크기-1까지)이 아니라,

입력값이 배열 순서가 되도록 만들었다.(입력값이 10이라면 배열[10]가 +1이 되는 식)

(오름차순을 쉽게 만드는 원리)

그리고 나머지는 소스에 주석을 참고하면 되겠다!

* 풀이 소스 

 
public class Baekjoon2108 {
 
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[] positiveArray = new int[4001]; // 입력값 양수 배열
        int[] negativeArray = new int[4001]; // 입력값 음수 배열
        int[] ascendArray = new int[N]; // 오름차순으로 배열된 입력값 배열
        
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int input = Integer.parseInt(st.nextToken());
            if(input >=0) {
                positiveArray[input]++;
            }else {
                negativeArray[-input]++;
            }
            
        }
        
        int ascendOrder = 0;
        int modeRoutine = 0; // 각 수들의 빈도 수(최빈값을 만들기 위해)
        List<Integer> modeList = new ArrayList<>(); // 최빈값이 들어갈 리스트
        double sum = 0.0;
        
        /* 계산 로직 상 음수 부분을 먼저 계산해주어야 전체 입력값이 오름차순으로 배열됨과 동시에 최빈값이 작은 수부터 순서대로 채워질 수 있다 */
        for(int j=negativeArray.length-1; j>0; j--) {
            
            
            if(negativeArray[j] != 0) { // 입력값이 들어간 부분만 계산
                
                
                if(modeRoutine == negativeArray[j]) {// 반복한 횟수(최빈값을 구하기 위해)
                    modeList.add(-j); // 이 경우 최빈값이 여러개 나왔을 때다.
                    
                }else if(modeRoutine < negativeArray[j]) {
                    modeRoutine = negativeArray[j];
                    modeList = new ArrayList<>(); // 빈도수가 더 많은 수가 나오면 기존의 리스트를 초기화한다.
                    modeList.add(-j);
                }
                
                while(negativeArray[j] != 0) {
                    sum -= j; // 총 합
                    ascendArray[ascendOrder++] = -j; // 오름차순 정렬
                    negativeArray[j]--; 
                }
                
                
            }
            
        }
        
        for(int k=0; k<positiveArray.length; k++) {
            
            if(positiveArray[k] != 0) { // 입력값이 들어간 부분만 계산
                
                if(modeRoutine == positiveArray[k]) {// 반복한 횟수(최빈값을 구하기 위해)
                    modeList.add(k); // 이 경우 최빈값이 여러개 나왔을 때다.
                    
                }else if(modeRoutine < positiveArray[k]) {
                    modeRoutine = positiveArray[k];
                    modeList = new ArrayList<>(); // 빈도수가 더 많은 수가 나오면 기존의 리스트를 초기화한다.
                    modeList.add(k);
                    
                }
                
                while(positiveArray[k] != 0) {
                    sum += k; // 총 합
                    ascendArray[ascendOrder++] = k; // 오름차순 정렬
                    positiveArray[k]--;
                }
                
            }
        }
        
        bw.write(String.valueOf(Math.round(sum/N))+"\n"); // 문제 조건의 소수점자리 감안해서 계산
        bw.write(String.valueOf(ascendArray[(N-1)/2])+"\n");
        if(modeList.size() == 1) { // 최빈값이 하나 밖에 없다면 그것을 출력.
            bw.write(modeList.get(0)+"\n");
        }else { // 최빈값이 여러개일 경우, 두번째로 작은 값
            bw.write(modeList.get(1)+"\n");
        }
        bw.write(String.valueOf(ascendArray[N-1]-ascendArray[0]));
        bw.flush();
        
    }
 
}