평균, 중위값, 최빈값, 범위 구하기 C++ / JAVA / 파이썬 정렬 시간복잡도

백준 2108번 통계학 문제를 풀면서 각 언어별로 평균, 중위값, 최빈값, 범위를 구하는 알고리즘을 알아봅시다.

 

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

2108번: 통계학

 

 

문제에 산술평균, 중앙값, 최빈값, 범위를 구하는 방법이 나와있습니다.

정수의 범위는 절대값 4000이므로 -4000에서 4000까지의 값을 갖습니다.

수의 개수는 500,000으로 정렬을 사용해도 시간초과가 나지 않고 충분합니다.

정렬 시간복잡도 : O(NlogN)

 

1. JAVA

1) 평균 구하기

a라는 배열에 숫자를 저장합니다.

저장과 동시에 sum이란 변수에 합을 구합니다. 

sum을 double로 지정하는 이유는 평균을 구하기위해 n으로 나눠주고 소수점 첫째자리에서 반올림 하기 위함입니다.

int로 지정하면 자동 형변환이 안되어 오차가 생기고 답을 틀리게 됩니다. 

 

2) 중앙값 구하기

a 배열을 정렬하고 n/2 위치의 값이 중앙값입니다.

 

3) 최빈값 구하기

가장 많이 나오는 숫자를 카운팅합니다. -4000 ~ 4000 이므로 배열을 8001을 선언합니다.

그리고 많은 숫자를 출력합니다. 만일 2개 이상이면 그 다음 작은 값을 출력합니다. check 변수를 활용해서 for 한번에 2번째 값까지 찾을 수 있습니다.

 

4) 범위 구하기

정렬한 a 배열의 가장 큰값에서 작은 값을 빼면 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		int[] a = new int[n];
		int[] count = new int[8001];
		
		double sum = 0;
		
		for(int i = 0; i<n; i++){
			a[i] = Integer.parseInt(br.readLine());
			sum += a[i];
			count[a[i] + 4000]++;
		}
		
		Arrays.sort(a);
		
		int countMax = Integer.MIN_VALUE;
		int countAns = 0;
		int check = 0;
		for(int i = 0; i < 8001; i++) {
			if(countMax < count[i]) {
				countAns = i - 4000;
				countMax = count[i];
				check = 1;
			}else if(count[i] == countMax && check == 1) {
				countAns = i -4000;
				check = 0;
			}
		}
			
		System.out.println(Math.round(sum / n));
		System.out.println(a[n/2]);
		System.out.println(countAns);
		System.out.println(a[n-1] - a[0]);
	}
}

 

2. C++

그냥 풀면 재미가 없으므로 이번에는 sum을 int로 선언했습니다.

마지막 답을 구할 때 (double)을 추가하여 형변환 합니다.

그래야 답이 맞습니다.

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

	int a[n] = {0};
	int count[8001] = {0};
	
	int sum = 0;

    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
        count[a[i]+4000]++;
    }

	sort(a, a + n);
	
    int countMax = -987654321;
	int countAns = 0;
	int check = 0;
    for(int i = 0; i < 8001; i++){
		if(countMax < count[i]) {
			countAns = i - 4000;
			countMax = count[i];
			check = 1;
		}else if(count[i] == countMax && check == 1) {
			countAns = i -4000;
			check = 0;
		}
    }

    cout << (int)round((double)sum/(double)n) << "\n" << a[n/2] << "\n" << countAns << "\n" << a[n-1] - a[0];

    return 0;
}

 

 

3. Python 파이썬

파이썬은 함수가 많아서 코드 길이가 짧습니다.

collections을 import하고 Counter에 정렬한 배열 a를 넣습니다.

그리고 most_common() 함수를 사용해서 c에 저장합니다.

c에는 (값, 개수) 튜플 형태로 데이터가 들어갑니다. 

java와 C++에서 어렵게 풀이했던 최빈값을 사기적으로 간단하게 풀었습니다.

import sys
import collections

n = int(sys.stdin.readline())

a = sorted([int(sys.stdin.readline()) for _ in range(n)])

c = collections.Counter(a).most_common()

if n == 1 : 
    cA = c[0][0]
else :
    if c[0][1] == c[1][1] :
        cA = c[1][0]
    else :
        cA = c[0][0]
print(round(sum(a)/n), a[n//2], cA, a[n-1] - a[0], sep = '\n')