[2108] 통계학

📖 문제

✏️ 풀이과정

문제를 보고 처음에 정수를 입력받을때 정수들의 합을 계산해서 산술평균 을 구하고, 배열에 저장한 다음 정렬 후에 중앙값 범위 를 구했다. 그리고 정수의 개수들을 카운팅해서 최빈값 처리를 따로 해줬다. 가장 고민했던 문제는 정수가 양의 정수 만 있는게 아니라 모든 정수 범위이기 때문에 음의 정수 에 대해서 빈도수를 카운팅하는 배열 인덱싱이었다. 정수의 절댓값의 범위가 크지 않아 모든 수에 +4000 을 해줘서 0~8000 까지의 범위로 데이터를 다뤘다.

⭕️ 풀이방법1

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        double sum = 0;
        int[] arr = new int[N];
        int[] cnt = new int[8001];
        for(int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            arr[i] = num;
            sum += num;
            cnt[num+4000]++;
        }

        Arrays.sort(arr);

        StringBuilder sb = new StringBuilder();
        // 산술평균
        sb.append(Math.round(sum/N)).append("\n");

        // 중앙값
        sb.append(arr[N/2]).append("\n");

        // 최빈값
        int freq = -1, mode = 0, tmp = 0;
        boolean dup = false;
        for(int i = 0; i < cnt.length; i++) {
            if(cnt[i] == 0) continue;

            int num = i-4000;

            if(cnt[i] > freq) {
                mode = num;
                dup = false;

                freq = cnt[i];
            }
            else if(!dup && cnt[i] == freq) {
                tmp = num;
                dup = true;
            }
        }
        sb.append(dup ? tmp : mode).append("\n");

        // 범위
        sb.append(arr[N-1]-arr[0]).append("\n");

        System.out.print(sb);
    }
}

여차저차 풀긴 풀었지만 가독성도 좋지 않고 무엇보다 불필요한 연산을 많이 한다. 정렬을 위한 배열이든 최빈값을 구하기 위한 배열이든 실제 정수의 개수가 몇 개인지 상관 없이 기본적으로 최소 8000 번의 루프를 돌고, Arrays.sort() 정렬 시간 복잡도는 O(nlogn) 을 기대할 수 있지만 최악의 경우 O(n^2) 의 시간 복잡도를 가진다.

⭕️ 풀이방법2

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int sum = 0;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        int median = 0, mode = 0;

        int[] arr = new int[8001];
        for(int i = 0; i < N; i++) {
            int val = Integer.parseInt(br.readLine());
            sum += val;
            arr[val+4000]++;

            if(val > max) max = val;
            if(val < min) min = val;
        }

        int cnt = 0, freq = 0;
        boolean flag = false;
        for(int i = min+4000; i <= max+4000; i++) {
            // 중앙값
            if(cnt < (N + 1) / 2) {
                cnt += arr[i];
                median = i - 4000;
            }

            // 최빈값
            if(arr[i] > freq) {
                freq = arr[i];
                mode = i-4000;
                flag = true;
            }
            else if(flag && arr[i] == freq) {
                mode = i-4000;
                flag = false;
            }
        }
        

        System.out.println(Math.round((double)sum/N));
        System.out.println(median);
        System.out.println(mode);
        System.out.println(max-min);
    }
}

중앙값 과 범위 를 위한 배열을 사용하지 않았다. 정수를 입력받을때 최댓&최솟값 도 같이 구해줬다. 그리고 최빈값 을 구하는 루프 안에서 중앙값 을 같이 구해줬다. 가장 작은 수 부터 숫자들이 몇 번씩 나왔는지 카운팅 하다가 카운트 값이 입력받은 정수 개수의 절반보다 커질 경우 중앙값을 넘어간 것이기 때문에 더이상 처리하지 않고 가장 마지막에 카운트한 정수를 중앙값으로 저장한다.

💻 참고코드

• dltkdgns830. [제출번호] 30173444

👩🏻‍💻 생각정리

무조건 알고리즘 분류대로 풀려고 하지 말자.. 사실 이 문제는 정렬밖에 생각 안났다🙄 불필요한 연산이 많다 싶으면 어떻게 하면 연산을 줄일 수 있을까 생각하며 다른 방법들도 생각해보자.