[백준] 2108 - 통계학 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

 

---

링크

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

2108번: 통계학

문제

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

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

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

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

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

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

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

접근방법

 문제에서 요구하는 4가지의 값을 출력하는 문제이다. 평균, 중앙값, 범위는 어렵지 않게 구할 수 있다. 하지만, 문제에서 최빈값에 대해서는 여러 개가 있을 경우에 대한 예외처리를 요구한다. 최빈값을 어떻게 구할 것인가에 대해 생각하고 풀이에 들어가자.

풀이

 평균과 중앙값, 범위는 아래와 같이 쉽게 정리하고, 구현할 수 있다.

 

• 평균 = 총합 / N의 개수
• 중앙값 =  size의 절반
• 범위 = 정렬 후 0번 인덱스부터 마지막 인덱스까지의 범위

그렇다면 최빈값은 어떻게 구해야 할까? 일단 최빈값의 정의부터 알아보자.

 

최빈값 = 가장 많이 나타나는 수

 

중복되는 숫자가 들어올 수 있기 때문에, 숫자들의 개수도 파악을 해야 한다. 나는 이 부분을 위해서 Hashmap을 이용했다. Key값으로 숫자를 준다면, 빠르게 찾아 value값으로 개수를 조절하기 쉽기 때문이다. 단, 문제는 최빈값이 여러개일 경우이다. '최빈값이 여러개다.'의 의미는 숫자들의 갯수가 같은 숫자들이 여러개 라는 것이다. 이 때 이러한 최빈값들에 대해 두번째로 작은 값을 구해야한다. 결국 최빈값들에 대한 정렬을 시행해야하고, 그 중에 두번째를 뽑아내야 한다는 것이다.

 

나는 2차 정렬을 사용하여, 최빈값을 정리했다. HashMap의 value 값인 갯수를 가지고 내림차순으로 정리하되, value값이 같은 경우, 오름차순으로 정렬했다. (지금 생각해보니, 이미 이렇게 만든 리스트에서 조건 처리를 해도 최빈값을 도출하는데 문제가 없었을 텐데... 최빈값이 하나인지 여러 개 인지 판단하기 귀찮아서, 우선순위 큐에 넣고 쓴듯하다...)

코드

import java.util.*;

public class BJ_2108 {

    public static void main(String[] args) {
        BJ_2108 test = new BJ_2108();
    }

    public BJ_2108() {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();

        int[] datas = new int[cnt];

        for (int i = 0; i < cnt; i++) {
            datas[i] = sc.nextInt();
        }

        Arrays.sort(datas);
        solution(datas);

    }


    public int[] solution(int[] datas) {
        int sum = 0;
        int avr, median, mode, range;
        int[] result= new int[4];
        LinkedHashMap<Integer,Integer> hashMap = new LinkedHashMap<>();
        for (int data : datas) {
            if(hashMap.isEmpty()){
                hashMap.put(data,1);
            }else if(hashMap.containsKey(data)){
                hashMap.put(data,hashMap.get(data)+1);
            }else{
                hashMap.put(data,1);
            }
            sum += data;
        }

        //산술 평균
        avr = (int)Math.round((double) sum / datas.length);

        //중앙값
        median = datas[datas.length/2];

        //범위
        range = datas[datas.length-1] - datas[0];

        List<Integer> lst = new ArrayList<>(hashMap.keySet());

        /*
        요구 하는 최빈값 조건
        1순위 - 가장 많은 횟수
        2순위 - 가장 많은 횟수가 두개 이상 이면, 최빈값 중 두 번째로 작은 값
         */
        
        //데이터가 하나일 땐 하나가 최빈값
        if(datas.length==1){
            mode = datas[0];

        }else{
            //lst 정렬 기준 1차 정렬 - 최빈값 순서
            //2차 정렬 - 최빈값이 같다면 오름차순
            Collections.sort(lst,(o1, o2) -> {
                if(hashMap.get(o1).equals(hashMap.get(o2))){
                    return o1.compareTo(o2) ;
                }else{
                    return hashMap.get(o2).compareTo(hashMap.get(o1));
                }
            });

            PriorityQueue<Integer> queue = new PriorityQueue<>();

            //최빈값이 같은 경우만 우선순위 큐에 넣음
            for (int i = 0; i <lst.size() ; i++){
                if(queue.isEmpty()){
                    queue.offer(lst.get(i));
                }else{
                    if (hashMap.get(queue.peek())>hashMap.get(lst.get(i))){
                        break;
                    }
                    queue.offer(lst.get(i));
                }

            }

            //최빈값이 하나라면 바로 out
            if(queue.size()==1){
                mode = queue.peek();
            }else{
                //최빈값이 여러개라면 두번쨰로 작은 녀석 출력
                queue.poll();
                mode = queue.peek();
            }

        }
        
        System.out.println(avr);
        System.out.println(median);
        System.out.println(mode);
        System.out.println(range);


        return result;
    }
}

결과

 메모리와 시간이 만족스럽지는 않지만, HashMap을 이용해서는 최선인 듯하다. 카운팅 정렬을 이용하여, 사용할까 했지만, 8000개의 배열(최대 값 - 절댓값 4000)을 만들어 카운팅 정렬하는 것이 비효율적이라 생각하여, Hashmap접근이 더 이득이라고 생각했는데.. 결과는 내쪽이 훨씬 느렸다..

 

중간에 런타임 에러로 IllegalArgument 에러와 좀 많이 만났는데, Collections.sort() 과정에서 Comparator를 정의한 부분에서 모호함이 발생했기 때문이었다.  백준 런타임 에러 헬프 가이드를 찾다 보니, 아마도 정의한 정렬 조건 중 같다는 부분을 처리 안 해서 나오는 모호함 때문에 발생한 것 같다. Comparator를 정의할 때는 다음과 같은 사실을 만족하는지 염두에 두면, 좋을 것 같다.

 

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.