[알고리즘] 백준 2108 통계학 Java

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

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

산술평균 : N개의 수들의 합을 N으로 나눈 값
중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
최빈값 : N개의 수들 중 가장 많이 나타나는 값
범위 : N개의 수들 중 최댓값과 최솟값의 차이
N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

예제 입력 1

5
1
3
8
-2
2

예제 출력 1

2
2
1
10

예제 입력 3

5
-1
-2
-3
-1
-2

예제 입력 3

-2
-2
-1
2

Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.io.IOException;

public class Main{
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int sum = 0;
        ArrayList<Integer> list = new ArrayList<>();

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

            sum += temp;

            if(temp > max){
                max = temp;
            }
            if(temp < min){
                min = temp;
            }
            list.add(temp);
        }

        Collections.sort(list);

        Map<Integer, Integer> countMap = new HashMap<>();
        int maxCount = -1;
        for (Integer num : list) {
            Integer count = countMap.get(num);
            if(count == null){
                count = 1;
                countMap.put(num, count);
            } else{
                countMap.put(num, ++count);
            }

            if(count != null && count > maxCount){
                maxCount = count;
            }
        }

        ArrayList<Integer> modeList = new ArrayList<>();

        for(Integer key: countMap.keySet()){
            Integer value = countMap.get(key);
            if(value == maxCount){
                modeList.add(key);
            }
        }

        Collections.sort(modeList);
        int mode;
        if(modeList.size() == 1){
            mode = modeList.get(0);
        } else{
            mode = modeList.get(1);
        }

        int average =((int)Math.round((double)sum / N));

        int middle = list.get(N/2);

        sb.append(average + "\n");
        sb.append(middle + "\n");
        sb.append(mode + "\n");
        sb.append(max - min + "\n");

        System.out.println(sb);
    }
}

Point

이 문제에 대한 접근을 처음에는 배열로 접급하였다가, 최빈값 구하는 부분에서 너무 복잡해지기에 포기했다.

그렇기에 ArrayList를 사용하여 풀었고, Collections.sort()를 사용하여 정렬을 해주었다.

아마 다들 최빈값을 구하는 부분에서 막힐건데, 필자는 HashMap을 통해서 key, value 형식으로 저장하여, 가장 많이 출력된 값들은 새로운 ArrayList에 저장해 주어 최빈값을 구하도록 하였다.

처음 배열을 이용하여 풀 때에는 입력 숫자의 갯수를 count하여 새로운 배열에 저장하고 그 인덱스로 비교하며 출력하려하니 꽤나 복잡해지기에 위의 방식을 이용하여 풀었더니 훨씬 쉬웠다.

그럼에도 문제의 정답률은 25.419%로 낮고, 입력되는 테스트케이스의 수는 5십만개로 ArrayList를 이용하여 풀면 시간 제한에 걸릴 수도 있겠다 라는 생각을 갖고 일단 제출을 해보자 생각하고 제출을 하였더니 시간은 의외로 얼마 나오지 않았다.

위의 방식으로 풀 경우 시간은 1172ms가 나오게 된다.

만약 시간제한이 더 빡빡해진다면, 그때는 배열을 이용하여 풀어야 할 것 같다.