[BOJ/Step12] 2108 : 통계학 (JAVA)

www.acmicpc.net/problem/2108

2108번: 통계학

---

문제

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

- 산술평균 : N개의 수들의 합을 N으로 나눈 값

- 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값

- 최빈값 : N개의 수들 중 가장 많이 나타나는 값

- 범위 : N개의 수들 중 최댓값과 최솟값의 차이

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

 

입력

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

 

출력

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

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

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

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

 

예제 입력 1

5

1

3

8

-2

2

 

예제 출력 1

2

2

1

10

 

예제 입력 2

1

4000

 

예제 출력 2

4000

4000

4000

0

 

예제 입력 3

5

-1

-2

-3

-1

-2

 

예제 출력 3

-2

-2

-1

2

---

풀이

산술평균과 중앙값, 최빈값, 범위를 구하는 문제

=> 카운팅 정렬 알고리즘 이용

 

산술평균은 입력받은 값을 모두 더해 개수로 나누면 되고

중앙값은 정렬 후 n/2 자리의 값이며

범위는 정렬 후 마지막 값 - 첫번째 값이다.

최빈값이 가장 까다롭다. 최빈값이 여러개 일 때 두 번째로 작은 값을 출력해야 하기 때문이다.

 

1. n개의 정수를 입력받는다.

   1-1. 이때 입력받아 배열에 저장함과 동시에 total 변수에 더해 총 합을 구해주고,

   1-2. 입력받는 값을 비교하여 최댓값과 최솟값을 max값과 mix값에 저장한다.

 

2. 산술평균과 범위를 구한다

   2-1. 입력이 끝나면 total을 n으로 나누어 산술평균을 구해준다.

           주의할 점은 total을 double 형으로 선언해 주어야 n으로 나누는 과정에서 소수점이 날아가지 않는다.

           소수점 첫째자리에서 반올림 해야 하기 때문에 Math.round() 메소드를 사용한다.

   2-2. max값과 min값을 이용해 범위를 구해준다. (max - min)

 

카운팅 정렬을 이용해 최빈값을 구해보기로 한다.

기존 카운팅 정렬은 상수값만 정렬할 수 있었지만, 이를 변형하여 음수값도 정렬이 가능하도록 해 준다.

앞에서 구한 min 값을 배열의 0, max 값을 배열의 마지막 위치라고 가정, 범위+1 크기의 배열 count를 만들어 빈도수를 셈 해주는 방식을 사용할 것이다.

예제 1과 같이 -2 ~ 8 까지의 수가 주어진다면 범위는 10, 크기 11인 배열을 만들어 카운팅 해준다.

 

3. 2-2에서 구한 범위를 이용해 범위+1 크기의 count 배열을 만들어 빈도수를 저장한다.

    빈도수를 셀 때, 카운팅 정렬과 같이 해당 숫자와 같은 배열 인덱스에 접근할 수는 없다. 숫자가 음수일 수도 있기 때문이다.

    예제 1에서는 -2는 배열[0]에, 8은 배열[10]에 저장될 것이다. [숫자 - 최솟값] 이 해당 숫자의 인덱스가 됨을 알 수 있다.

이제 각 수의 빈도수를 배열에 저장하였다.

 

4. count 배열 중 가장 큰 값이 뭔지 찾는다. 두번째로 작은 숫자인지 확인할 num, 최빈값의 인덱스를 저장할 mode_idx   4-1. 최빈값의 인덱스를 변수 mode_idx에 저장한 후 for문 안에서 count 배열을 순회하며 비교한다.   4-2. if (count[mode_idx] == count[i])일 때 for문을 탈출한 후 그 인덱스를 출력하면 되겠다고 생각했는데 혹시 그 숫자가 최빈값이 아니면 어떡하지 하는 생각이 들었다.           그래서 조건을 추가했다. if(count[mode_idx] == count[i] && num == 1)일 때, mode_idx = i, num++을 해준다.   4-3. if(count[mode_idx] < count[i] && count[mode_idx] != count[i])일 때, mode_idx = i, num = 1을 해준다.=> 카운트 배열 값을 비교하고, 가장 큰 값의 인덱스가 mode_idx 에 저장된다. 가장 큰 값이 중복으로 나올 경우, 두번째 값만 저장하기 위해서 num이 1일 때만 num을 증가시켜준다. 또한 배열 뒷부분에 더 큰 값이 나올 수 있으므로 더 큰 값을 발견한 경우엔 num 값을 1로 바꿔준다.for문 수행이 끝나면 mode_idx에 최빈값이 저장되었을 것이다. 이를 이용해 최빈값을 구해준다. min값을 더해주어야 한다.

 

5. count 배열의 빈도수를 누적해서 더해주고,

 

6. 입력 배열의 역순으로 배열b에 요소를 채워넣는다.    

이때, 빈도수를 셀 때와 마찬가지로 해당 숫자 그대로 배열 인덱스에 접근하면 오류가 날 수 있기 때문에 숫자 - 최솟값 으로 배열에 접근해야만 한다.

 

7. 배열 b를 기존 배열에 복사한다.

 

8. 정렬된 배열[n/2] 에 위치한 중앙값을 저장

 

9. 산술평균과 중앙값, 최빈값, 범위를 차례로 출력한다.

 

import java.io.*;

public class B2108 {

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

		int n = Integer.parseInt(br.readLine());
		int[] sort = new int[n];
		double total = 0;
		
		for(int i = 0; i < n; i++) {
			sort[i] = Integer.parseInt(br.readLine());
			total += sort[i];
		}
		
		int max = sort[0];
		int min = sort[0];
		for(int i = 0; i < n; i++) {
			if(sort[i] > max)
				max = sort[i];
			if(sort[i] < min)
				min = sort[i];
		}
		
		int i1 = (int)Math.round(total / n);	// 산술평균
		int i2 = 0;								// 중앙값
		int i3 = 0; 							// 최빈값
		int i4 = max - min;;					// 범위
		
		int[] count = new int[i4+1];
		int[] b = new int[n];
		
		for(int i = 0; i < sort.length; i++) {
			count[sort[i] - min]++;
		}
		
		int mode = -1;
		int num = 1;
		int mode_idx = 0;
		for(int i = 0; i < count.length; i++) {
			if(mode == count[i] && num == 1) {
				mode_idx = i;
				num++;
			}
			if(mode < count[i] && mode != count[i]) {
				mode = count[i];
				mode_idx = i;
				num = 1;
			}
		}
		i3 = mode_idx+min;
		
		for(int i = 1; i < i4+1; i++) count[i] += count[i-1];
		for(int i = n-1; i >= 0; i--) b[--count[sort[i] - min]] = sort[i];
		for(int i = 0; i < n; i++) sort[i] = b[i];

		i2 = sort[n/2];				
						
		System.out.println(i1);
		System.out.println(i2);
		System.out.println(i3);
		System.out.println(i4);
	}
}