[BackJoon]2108번 카운팅 정렬로 풀기

문제

 

수를 처리하는 것은 통계학에서 상당히 중요한 일이다.

통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다.

단, N은 홀수라고 가정하자.

 

• 산술평균 : N개의 수들의 합을 N으로 나눈 값
• 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
• 최빈값 : N개의 수들 중 가장 많이 나타나는 값
• 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 

단, N은 홀수이다. 

그다음 N개의 줄에는 정수들이 주어진다. 

입력되는 정수의 절댓값은 4,000을 넘지 않는다.

 

출력

 

첫째 줄에는 산술평균을 출력한다. 

소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

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

셋째 줄에는 최빈값을 출력한다. 

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

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

 

풀이

 

숫자의 개수는 많지만 범위는 좁다. 누가 봐도 카운팅 정렬을 응용하라는 문제이다.

 

하지만 그냥 스트림만 사용해 단순히 풀고 싶어서.. 거의 반나절을 날려먹고

 

버전 3에서 카운팅 정렬을 사용해서 통과했다.

 

입력값의 범위가 -4000에서 4000이므로, 먼저 수의 개수만 한 크기의 target 배열을 만들어

 

입력값에 4000을 더해 저장해 주었다(음수 보정).

 

이어서 크기가 8001인 counting 배열을 생성하고 카운팅을 진행한 이후 스트림을 이용해 최빈값을 뽑아냈다.

 

계속해서 counting 배열을 누적합으로 바꿔주고, 정렬.

 

기회만 있으면 쓰려고 하는 summarizingInt() 메서드를 이용해 평균, 최대, 최소를 한 번에 구하고

 

정렬이 끝난 배열이기 때문에 중앙값을 바로 구했다.

 

사실 이미 정렬이 끝났기 때문에 스트림으로 최대, 최소를 구할 필요는 전혀 없지만

 

평균을 위해 스트림을 여는 김에 한 번 사용해 보았다.

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Prob2108_3 {

    private static int[] result;
    private static int mode;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int[] target = new int[n];

        for (int i = 0; i < n; i++) {
            target[i] = Integer.parseInt(br.readLine()) + 4000;
        }

        countingSortImpl(target);
        
        IntSummaryStatistics stat = Arrays.stream(result)
                .map(a -> a - 4000)
                .boxed()
                .collect(Collectors.summarizingInt(a -> a));

        int median = result[n / 2] - 4000;

        bw.write(Math.round(stat.getAverage()) + "\n");
        bw.write(median + "\n");
        bw.write(mode + "\n");
        bw.write(stat.getMax() - stat.getMin() + "\n");

        bw.flush();
        bw.close();
    }

    public static void countingSortImpl(int[] target) {

        int[] counting = new int[Arrays.stream(target).max().getAsInt() + 1];
        result = new int[target.length];

        for (int i = 0; i < target.length; i++) { // Counting
            counting[target[i]]++;
        }

        List<Integer> sortedList = Arrays.stream(counting)
                .boxed()
                .sorted(Comparator.reverseOrder())
                .collect(Collectors.toList());

        if (sortedList.get(0).equals(sortedList.get(1))) {

            mode = Arrays.stream(target)
                    .filter(a -> counting[a] == sortedList.get(0))
                    .distinct()
                    .boxed()
                    .sorted()
                    .skip(1)
                    .findFirst()
                    .get() - 4000;

        } else {
            mode = IntStream.of(counting).boxed().collect(Collectors.toList()).indexOf(sortedList.get(0)) - 4000;
        }

        for (int i = 1; i < counting.length; i++) { // 누적 합
            counting[i] += counting[i - 1];
        }

        for (int i = target.length - 1; i >= 0; i--) { // 정렬
            counting[target[i]]--; // 해당 인덱스 값을 하나 줄여주고
            result[counting[target[i]]] = target[i]; // 줄여진 수를 인덱스 삼아 result에 값 채우기
        }
    }
}