[백준] 2108번: 통계학 [C++]

 

알고리즘 분류: 수학, 구현, 정렬

문제 링크: https://www.acmicpc.net/problem/2108

2108번: 통계학

 

 

【 문제 】

 

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

 

1.  산술평균: N개의 수들의 합을 N으로 나눈 값
2.  중앙값: N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3.  최빈값: N개의 수들 중 가장 많이 나타나는 값
4.  범위: N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

 

 

 

【 입력 】

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

 

 

 

【 출력 】

 

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

 

 

【 풀이 】

 

4개의 통계값을 구하는 문제이다.

우선, 입력값을 저장받기 위한 벡터와 계수정렬(Counting Sort) 알고리즘을 이용해 입력받은 숫자들의 등장 횟수를 저장하는 배열 cnt를 선언한다.

그 후 입력값을 저장한 벡터를 정렬한 다음 4개의 통계값을 구해주면 된다.

 

1. 산술평균: 평균을 의미한다. 처음 값을 입력받을 때부터 값들의 합을 구해주고 n으로 나눠준다. 하지만 여기서 함정은, 마지막에 나온 값은 반올림해야 하고 '-0'이 출력되면 안 된다. 반올림의 경우는 cmath 헤더에서 지원하는 round(반올림 함수), floor(내림 함수), ceil(올림 함수) 등을 이용하면 된다.
2. 중앙값: 말 그대로 배열의 중앙값을 의미한다. n이 홀수라고 이미 가정되었으니, 배열 사이즈의 1/2에 해당하는 인덱스의 값을 구해주면 된다. 
3. 최빈값: 가장 많이 나온 숫자를 의미한다. 계수정렬 알고리즘을 이용하여 배열에 횟수를 저장하면, 그 배열의 최댓값의 인덱스가 곧 최빈값이 된다. 같은 값이 있으면 두 번째로 작은 수를 출력하라고 하였으니, 이 경우에는 최댓값이 같은 경우를 카운트해 주어서 카운트 값이 2가 될 때의 인덱스를 저장하면 된다.
4. 범위: 정렬을 해놓으면 자연스럽게 처음이 최솟값이 되고, 마지막이 최댓값이 되므로 "첫 인덱스 - 마지막 인덱스"가 범위의 값이 되겠다.

 

이 문제는 최빈값 때문에 굉장히 껄끄럽게 느껴진다. 그러나 최빈값의 경우에도 예외처리만 잘해주면 쉽게 구할 수 있다.

 

 

 

【 코드 】

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;


int main(void)
{
	vector<double>stat;
	int cnt[8002] = { 0 };		//	최빈값을 저장하기 위한 배열
	int count = 0;
	double avg, medi, many, range;
	double sum = 0;
	int n, i;
	int max = -5555;

	cin >> n;

	for (i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		sum += num;
		stat.push_back(num);
		if (num == 0)
			cnt[4000]++;
		else
			cnt[num + 4000]++;
	}

	sort(stat.begin(), stat.end());

	for (i = 0; i < 8002; i++)
	{
		if (cnt[i] == 0)
			continue;
		if (max < cnt[i])
			max = cnt[i];
	}
	for (i = 0; i < 8002; i++)
	{
		if (max == cnt[i])
		{
			many = i - 4000;
			count++;
		}
		if (count == 2)		//	최빈값이 여러개일 경우
			break;
	}

	avg = sum / n;
	medi = stat[stat.size() / 2];
	range = stat.back() - stat.front();

	if (round(avg) == -0)
		cout << 0 << '\n' << medi << '\n' << many << '\n' << range;
	else
		cout << round(avg) << '\n' << medi << '\n' << many << '\n' << range;
	return 0;
}