백준 2108번 통계학(Java)

보기엔 쉬워보였지만 막상 풀어보니 최빈값 구하는데 시간이 매우 많이 들었다.

산술평균은 Math.round()를 써서 반올림을 했다. 

최빈값을 제외한 나머지는 정렬해서 정렬하 위치에 값에 따라 계산을 해 풀었다.

이 문제의 핵심인 최빈값은 다른 풀이들은 모두 int형 8001개의 배열에 각 index에 해당하면 값을 +1씩 해주는 식으로 풀었지만, 나는 그게 웬지 싫어서 다른방식으로 풀어보았다. 백준에서는 시간오버가 뜨긴 했지만 작동은 잘 되긴 한다.

 

최빈값 풀이 방법

 

배열 list가 있다고 하자

1

3

6

3

2

4

1) 이 배열을 Arrays.sort(list)로 정렬

1

2

3

3

4

6

 

2) 정렬을 한 후 중복되지 않는 수의 배열과 해당 수들에 개수의 배열을 만든다. 

 

num_list

count_list

list

1

2

3

3

4

6

 

3) num_list에 해당 list[0]의 수가 들어가 있는지 검사한 후 만약 들어가 있지 않다면, num_list에 list[0]을 넣고,count_list에 0을 넣는다.

list

1

2

3

3

4

6

num_list

1

count_list

0

 

4)num_list[0]의 값이 list에 들어있는지 검사한 후, 들어가 있으면, count_list 에 +1을 한다. 이때, list가 정렬이 되어있기에 count_list 인덱스의 값은 num_list의 index값의 개수다.

list

999999

2

3

3

4

6

num_list

1

count_list

1

 

5) list를 끝까지 다 돌았으면 list[2]의 값이 num_list에 있는지 확인하고 없으면 num_list에 추가한다. count_list도 0을 추가한다. 이때 999999이 들어가 있으면 패스 한다.

list

999999

2

3

3

4

6

num_list

1

2

count_list

1

0

 

6) 3~5를 계속 반복하면 list를 전부 끝까지 돌게 되면 num_list와 count_list가 만들어진다.

 

num_list

1

2

3

4

5

count_list

1

1

2

1

1

 

7) count_list에서 가장 큰 수를 구한다.

count_list_max_value=2

 

8)그리고 count_list에서 가장 큰 수를 가지고 있는 index의 개수를 구하고 해당 index를 구한다. 여기선 하나 밖에 없으므로 2가 반환될것이다.

 

9-1)이때 index개수가 하나일 시 해당 index를 num_list에 넣으면 된다.

 

9-2) 만약 count_list에서 아래와 같이 가장 큰 값을 가진 index의 개수가 여러개일시  해당 값을 가진 index중에 2번째로 작은것을 선택해야 한다.

num_list

1

2

4

5

count_list

1

2

2

2

10) 반복을 통해 해당 값을 가진 index를 찾으면 count+1을 한다. 이때 count=1로 지정한다.

count=1+1

num_list

1

2

4

5

count_list

1

2

2

2

                                 (이 분이 2번째로 작은 부분이 되므로)

이렇게 하면 2번쨰로 작은 최빈값을 구할 수 있다.

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

public 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[] list=new int[n];
        for(int i=0;i<n;i++){
            list[i]= Integer.parseInt(br.readLine());
        }
        Arrays.sort(list);
        Main bae=new Main();
        System.out.println(bae.avg(list));
        System.out.println(bae.middle_num(list));
        System.out.println(bae.count_num(list));
        System.out.println(bae.range(list));
    }
    int avg(int[] list){
        double sum=0;
        for(int i=0;i<list.length;i++){
            sum+=(double)list[i];
        }
        return (int)Math.round(sum/ list.length);
    }

    int middle_num(int[] list){
       return list[list.length/2];
    }

    int count_num(int[] list){
        int[] new_list=list.clone();
        List<Integer> num_list=new ArrayList<>();
        List<Integer> count_list=new ArrayList<>();
        int count=0;
        for(int i=0;i<new_list.length;i++){
            if(new_list[i]!=999999) {
                num_list.add(new_list[i]);
                count_list.add(0);
                for (int j = i; j < new_list.length; j++) {
                    if(num_list.contains(new_list[j])){
                        count_list.set(num_list.indexOf(new_list[j]),count_list.get(num_list.indexOf(new_list[j]))+1);
                        new_list[j]=999999;
                    }
                }
            }
        }
        for(int i=0;i<count_list.size();i++){
            if(count_list.get(i)==Collections.max(count_list))
                count++;
        }
        if(count==1)
            return (num_list.get(count_list.indexOf(Collections.max(count_list))));
        else{
            int count_num=1;
            for(int i=0;i<count_list.size();i++){
                if(count_list.get(i)==Collections.max(count_list)){
                    if(count_num==2)
                        return num_list.get(i);
                    count_num++;
                }
            }
            return 0;
        }
    }

    int range(int[] list){
        return list[list.length-1]-list[0];
    }
}