자바 백준 2108번 문제 - 통계학

문제 출처 : https://www.acmicpc.net/problem/2108

2108번: 통계학

 

 

 

 

풀이 )

내 블로그 카테고리에 시간복잡도 O(N)을 가진 정렬 풀이법이 있다.

바로 생각났다.

수의 크기보다 N이 크다.거기다가 구해야하는 문제들을 보니 카운팅 정렬 알고리즘으로 풀면 괜찮을 것 같다.

 

import java.util.*;
import java.io.*;
class Main {
	// 1 2 4 4 6 -> 0 1 1 0 2 0 1 (cntArr[4] = 2)
	public StringBuilder solution(int n, int sum, int min, int max, int[] cntArr) {
		StringBuilder sb = new StringBuilder();
		// 산술 평균 구하기
		int average = (int)Math.round((double)sum / n);
		
		int cSum = 0, mid = Integer.MIN_VALUE; // 중앙값 구할 때 쓰일 변수들 : 누적합과 중앙값 
		int freqMax = 0, freqValue = Integer.MIN_VALUE; // 최빈값 구할 때 쓰일 변수들 : 진행중인 최대빈도수와 최빈값 
		boolean first = false; // 최빈값 중 2번째로 작은 값 판별할 boolean
		for(int i=min+4000; i<=max+4000; i++) {
			if (cntArr[i] > 0) {
				// 중앙값 구하기 : 누적합을 통해 인덱스 위치 찾기 가능 , 중앙 인덱스 위치 기준 (n+1)/2
				if (cSum < (n+1)/2) {
					cSum += cntArr[i];
					mid = i - 4000;
				}
				// 최빈값 구하기 : 여러 개일 경우 최빈값 중 2번째로 작은 값 출력 -> boolean 이용해 구하기
				if (freqMax < cntArr[i]) {
					freqMax = cntArr[i];
					freqValue = i - 4000;
					first = true;
				}
				else if (freqMax == cntArr[i] && first == true) {
					freqValue = i - 4000;
					first = false;
				}
			}
		}
		sb.append(average).append('\n');
		sb.append(mid).append('\n');
		sb.append(freqValue).append('\n');
		sb.append(max-min);

		return sb;
    }

	public static void main(String[] args) throws IOException {
		Main T = new Main();
		//Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] cntArr = new int[8002];
		int sum = 0;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for(int i=0; i<n; i++) {
			// sum, min값, max값 체크하면서 cntArr 입력받기
			int value = Integer.parseInt(br.readLine());
			sum += value;
			if (min > value) min = value;
			if (max < value) max = value;
			cntArr[value + 4000]++;
		}
		br.close();
		System.out.println(T.solution(n, sum, min, max, cntArr));
	}
}