[백준 알고리즘][자바] 2108번 : 통계학(카운팅 정렬)

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

2108번: 통계학

 

이번 문제를 해결할 때는 카운팅 정렬을 사용합니다.

2022.05.07 - [Algorithm/Theory] - [Java] Counting Sort(카운팅 정렬)

[Java] Counting Sort(카운팅 정렬)

그 이유는 최빈값을 구할 때 여러 개가 있을 때는 두 번째로 작은 값을 출력해야 하는데 이것을 해결할 때 카운팅 정렬이 가장 적절하기 때문입니다.

 

 

풀이

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int[] counting_array = new int[8001]; // 정수 범위 : -4000~4000
		int sum = 0;
		int max = Integer.MIN_VALUE; // 최댓값
		int min = Integer.MAX_VALUE; // 최소값
		int center = 0; // 중앙값
		int freq = 0; // 최빈값
		
		for(int i = 0 ; i < N ; i++) {
			int num = Integer.parseInt(br.readLine());
			counting_array[num+4000]++;
			sum = sum + num;
			max = Math.max(max, num);
			min = Math.min(min, num);
		}

		int count = 0; // 빈도 수
		int freq_count = 0; // 최대 빈도 수
		boolean flag = false; // 최빈 값중 두번째로 작은 수를 출력하기 위한 플래그
		
		for(int i = min+4000 ; i <= max+4000 ; i++) {
			
			if(count < (N + 1) / 2) {
				count += counting_array[i];
				center = i - 4000;
			}
			
			if(freq_count < counting_array[i]) {
				freq_count = counting_array[i];
				freq = i - 4000;
				flag = true;
			}else if(freq_count == counting_array[i] && flag == true) {
				freq = i - 4000;
				flag = false;
			}
		}

		bw.write(String.valueOf((int)Math.round((double)sum / N)) + "\n");
		bw.write(String.valueOf(center) + "\n");
		bw.write(String.valueOf(freq) + "\n");
		bw.write(String.valueOf(max - min));
		
		
		br.close();
		bw.flush();
		bw.close();
	}
}

 

먼저, 빈도수를 체크를 위한 배열 counting_array는 음수 범위의 수를 체크 해야하기 때문에 크기를 8001로 할당해줍니다.

입력받은 숫자의 빈도 수를 체크해줌과 동시에 합계, 최댓값, 최솟값을 구해줍니다.

 

그다음 구해야 하는 것은 중앙값과 최빈값인데, 중앙값은 빈도수를 count에 누적시키면서 빈도 수가 절반 이상이 될 때까지 중앙값을 초기화해주며 구해줍니다.

 

두 번째로 최빈값에서 생각해주어야 하는 것은 최대 빈도 수가 하나 인경우와 두 개 이상인 경우입니다.

첫 번째로 if문에서 freq_count가 counting_array보다 작을 경우 freq_count에 빈도수를 초기화해주면서 freq에 최빈값을 초기화합니다. 이때 flag를 true로 바꿔주면서 최대 빈도 수가 한번 나타났다는 것을 명시합니다.

두 번째로 else-if문에서 freq_count와 counting_array가 같고 flag가 true일 때 최빈값을 초기화해주면서 flag를 false로 바꿔줍니다. flag를 false로 바꿔주어야지 세 번째로 작은 최빈값이 나와도 else-if문을 실행시키지 않습니다.