[백준/자바] 2587번 대표값2 - 카운팅 정렬

• 문제

어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + 30) / 5 = 170 / 5 = 34가 된다.

평균 이외의 또 다른 대표값으로 중앙값이라는 것이 있다. 중앙값은 주어진 수를 크기 순서대로 늘어 놓았을 때 가장 중앙에 놓인 값이다. 예를 들어 10, 40, 30, 60, 30의 경우, 크기 순서대로 늘어 놓으면 10 30 30 40 60 이 되고 따라서 중앙값은 30이 된다.

다섯 개의 자연수가 주어질 때 이들의 평균과 중앙값을 구하는 프로그램을 작성하시오.

 

 

• 코드

카운팅 정렬은 평균 시간복잡도가 O(n)으로 매우 빠른 편이고, 지금처럼 10, 20, .. , 90 이라는 9개의 규칙적인 수열에 대해 효율적일 거라고 생각해 선택했다. 

최댓값에 따라 속도가 영향을 받으므로 10, 20, .. , 90 은 0, 1, .. , 8로 변환해 사용했고 마지막에 평균값과 중앙값 계산할 때만 재변환했다. 

 

 

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

public class AverageMedian {

    //입력값: 숫자 5개 (100 미만인 10의 배수)
    //출력값: 평균, 중앙값
    //카운팅 정렬

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] input = new int[5]; //입력값 배열
        int[] countArray = new int[9]; //카운팅 배열 //10,20,..,90
        int[] result = new int[5]; //결과 배열

        //입력값 배열, 카운팅 배열에 추가
        for (int i=0;i<input.length;i++){
            input[i] = Integer.parseInt(br.readLine())/10-1; //30, 50, 90, 10, 70 => 2, 4, 8, 0, 6
            countArray[input[i]]++; //1,0,1,0,1,0,1,0,1
        }

        //카운팅 배열 => 누적합으로 수정
        for (int i=1;i<countArray.length;i++){
                countArray[i] += countArray[i-1]; //1,1,2,2,3,3,4,4
        }

        //카운팅배열 값-- & 결과배열[카운팅배열 값]에 카운팅배열 인덱스 대입
        for (int i=input.length-1;i>=0;i--){ //입력값 뒷인덱스부터 진행
            countArray[input[i]]--;
            result[countArray[input[i]]]=input[i]; // 0,2,4,6,8
        }

        //중앙값
        int med = (result[2]+1)*10;

        //평균
        int total=0;
        for (int i=0;i<input.length;i++){
            total+=(input[i]+1)*10;
        }
        int avg = total/5;

        System.out.println(avg);
        System.out.println(med);

    }

}