[Java] baekjoon_2108 : 통계학

수학, 구현, 정렬

통계학 : Silver3

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

2108번: 통계학

 

 

 

풀이

import java.io.*;

public class Main {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		for (int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(br.readLine());
		}

		// CountingSort
		int[] count = new int[8001];

		for (int i = 0; i < N; i++) {
			count[num[i] + 4000]++;
		}
		int value[] = count.clone();
		for (int i = 1; i < 8001; i++) {
			count[i] = count[i] + count[i - 1];
		}
		int sortNum[] = new int[N];
		for (int i = N - 1; i >= 0; i--) {
			int tmp = count[num[i] + 4000] - 1;
			sortNum[tmp] = num[i];
			count[num[i] + 4000] = tmp;
		}

		// 첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.
		int sum = 0;
		for (int i = 0; i < N; i++) {
			sum += num[i];
		}
		bw.write(Math.round(sum / (double) N) + "\n");

		// 둘째 줄에는 중앙값을 출력한다.
		bw.write(sortNum[N / 2] + "\n");

		// 두 번째로 작은 최빈값 출력
		int max = 0;
		int cnt = 0;
		int mode = 0;
		for (int i = 0; i < 8001; i++) {
			if (max < value[i]) {
				max = value[i];
			}
		}
		for (int i = 0; i < 8001; i++) {
			if (max == value[i]) {
				cnt++;
				mode = i - 4000;
			}
			if (cnt == 2) {
				break;
			}
		}
		bw.write(mode + "\n");

		// 넷째 줄에는 범위를 출력한다.
		bw.write((sortNum[N - 1] - sortNum[0]) + "\n");
		bw.close();
	}
}

 

 

Counting Sort 알고리즘

ㄴ Counting Sort는 각 요소의 빈도수를 세고, 그 빈도수를 기반으로 정렬을 수행하는 알고리즘이다.

 

1. count 배열 초기화

count 배열은 각 수의 빈도수를 기록하기 위한 배열이다. 
배열 크기는 8001로 설정되어 있는데, 이는 주어진 수의 범위가 -4000에서 4000까지이며, 0도 포함되어 있기 때문이다.
count[num[i] + 4000]은 입력된 수 num[i]를 배열의 인덱스로 매핑하여 해당 수의 빈도수를 1 증가시킨다.

 

2. count 배열 누적합 계산

누적합을 구하는 부분이다. 이를 통해 각 수의 누적 빈도수가 계산된다.
count[i]에는 i번째 수까지의 빈도수의 합이 저장된다.

 

3. 정렬된 결과 배열 생성

누적합을 사용하여 각 수를 정렬된 위치에 배치한다.
sortNum 배열에는 정렬된 수열이 저장된다.
수열을 뒤에서부터 순회하며 각 수의 정렬된 위치를 찾아 sortNum 배열에 저장한다.

 

ㄴ 이렇게 구현된 Counting Sort를 통해 주어진 수열을 정렬하고, 정렬된 결과는 sortNum 배열에 저장된다.

 

 

---

 

 

문제점 : 첫째 줄과 둘째 줄, 넷째 줄의 출력은 쉬웠다. 하지만 최빈값을 구하는 셋째 줄 부분에서 어려움을 겪었다. 그냥 최빈값만 구하면 되는 것이 아니라, 최빈값이 여러 개일 경우도 따져야 하는 문제여서 고난을 겪었다.

해결 방법 : 다른 블로그들을 참고했을 때, 최빈값의 핵심은 해당 숫자가 몇 번이나 중복됐는지 횟수를 세는 것이므로 여기에 카운팅 정렬이 가장 적절하다고 나와있어 해당 정렬을 이용하여 해결하였다.

깨달은 바 : 최빈값을 구해야할 경우, 정렬을 할 때 Counting Sort 방법을 이용하도록 해야겠다.