자바로 백준 2108 풀기

풀이)
기본적으로 이 문제를 풀기 위해서는 Counting Sort(카운팅 정렬)을 사용할 것이다. 물론 정렬을 쉽게 하기 위해 Arrays.sort 로 풀 수도 있지만 최빈값을 구하는 과정에 있어 '두 번째로 작은 값'을 출력해야하다보니 조금 복잡해진다. (사실상 중앙값 때문에 정렬을 해야하는 문제인데, 중앙값을 찾기 위해 직접 비교하면서 정렬을 하는 것은 비용소모가 크다.)

그래도 혹시 모르니 Arrays.sort 로 푸는 방법도 올리긴 하겠으나, 기본 토대는 카운팅 정렬을 사용할 것이다.

내 코드)

/*
  counting 정렬을 사용한 방법
  st-lab.tisotry.com
*/
 
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		// 입력값의 범위 : -4000 ~ 4000
		int[] arr = new int[8001];
		
		/*
		 *  sum = 총 합계 
		 *  max = 최댓값
		 *  min = 최솟값 
		 *  median = 중앙값
		 *  mode = 최빈값 
		 */
		int sum = 0;
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		// median 과 mode 는 -4000~4000 을 제외한 수로 초기화하면 된다.
		int median = 10000;
		int mode = 10000;
		
		for(int i = 0; i < N; i++) {
			int value = in.nextInt();
			sum += value;
			arr[value + 4000]++;
		
			if(max < value) {
				max = value;
			}
			if(min > value) {
				min = value;
			}
		}
		
		
		// 순회 
		int count = 0;	// 중앙값 빈도 누적 수 
		int mode_max = 0; 	// 최빈값의 최댓값  
		
		// 이전의 동일한 최빈값이 1번만 등장했을경우 true, 아닐경우 false
		boolean flag = false;	 
		
		for(int i = min + 4000; i <= max + 4000; i++) {
			
			if(arr[i] > 0) {
				
				/*
				 * <중앙값 찾기>
				 * 누적횟수가 전체 전체 길이의 절반에 못 미친다면 
				 */
				if(count < (N + 1) / 2) {
					count += arr[i];	// i값의 빈도수를 count 에 누적
					median = i - 4000;
				}
				
				/*
				 * <최빈값 찾기>
				 * 이전 최빈값보다 현재 값의 빈도수가 더 높을 경우 
				 */
				if(mode_max < arr[i]) {
					mode_max = arr[i];
					mode = i - 4000;
					flag = true;	// 첫 등장이므로 true 로 변경 
				}
				// 이전 최빈값 최댓값과 동일한 경우면서 한 번만 중복되는 경우 
				else if(mode_max == arr[i] && flag == true) {
					mode = i - 4000;
					flag = false;					
				}
			}
		}
		
		System.out.println((int)Math.round((double)sum / N));	// 산술평균 
		System.out.println(median);	// 중앙값 
		System.out.println(mode);	// 최빈값 
		System.out.println(max - min);	// 범위 
	}
 
}