[백준/BOJ] 2108번 통계학 (C/C++)

백준 온라인 저지(BOJ) 2108번 통계학
https://www.acmicpc.net/problem/2108

2108번: 통계학

* 사용언어 : C언어, C++
 

1. 문제

N개의 수를 대표하는 기본 통계값을 순서대로 출력
(산술평균, 중앙값, 최빈값, 범위)

 

2. 풀이

산술평균을 구하기 위해 round 함수를 구현했습니다.
round 함수는 양수일 경우 +0.5를 한 뒤 int로 형변환(내림)하고, 음수일 경우 -0.5를 한 뒤 int로 형변환 합니다.
 
만약 제출했을 때 2%에서 '틀렸습니다'가 나온다면 음수 처리를 제대로 못 해서 가능성이 높습니다.
(처음에 +0.5만 했을 때 계속 2%에서 틀리다가, 음수인 경우 -0.5한 이후 2%를 넘어 통과했습니다)
 
 
최빈값의 경우 -4,000 ~ 4,000의 숫자들 중 가장 많이 등장한 숫자를 확인해야 합니다.
이를 간편하게 처리하기 위해 8,001크기의 배열을 선언한 뒤
숫자에 + 4000을 해서 각각의 숫자가 배열의 index 값에 대응되도록 했습니다.
 
문제 조건에 따라 최빈값이 여러 개인 경우 두 번째로 작은 값을 출력하면 되기 때문에
단순하게 최빈값에 해당하는 숫자의 개수(modeCnt)가 2이상인 경우 2로 초기화했습니다.
 
그리고 저장해둔 cnt 배열을 작은 수부터 순차적으로 탐색한 뒤
2번째 숫자를 최빈값(mode)로 출력하게 했습니다. (1개인 경우 1번째)
 
이후 풀이는 아래 코드로 대체하겠습니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
2108_통계학
5052KB	116ms
*/
#include <cstdio>

const int LM = 500000;
const int NBASE = 4000;
const int NLM = NBASE * 2 + 1;
int N, n, a[LM], t[LM], cnt[NLM];
double sum;

int round(double v) {
	if (v > 0) v += 0.5;
	else v -= 0.5;
	return (int)v;
}

void mSort(int s, int e) {
	if (s >= e) return;

	int m = (s + e) / 2;
	mSort(s, m);
	mSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (a[i] < a[j]) t[k++] = a[i++];
		else t[k++] = a[j++];
	}

	while (i <= m) t[k++] = a[i++];
	while (j <= e) t[k++] = a[j++];

	for (i = s; i <= e; ++i) a[i] = t[i];
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &n);
		a[i] = n;
		sum += n;
		cnt[NBASE + n] += 1;
	}

	int modeCnt = 0, maxCnt = -1;
	for (int i = 0; i < NLM; ++i) {
		if (cnt[i] > maxCnt) {
			maxCnt = cnt[i];
			modeCnt = 1;
		}
		else if (cnt[i] == maxCnt) ++modeCnt;
	}
	if (modeCnt > 1) modeCnt = 2;

	int mode;
	for (int i = 0; i < NLM; ++i) {
		if (cnt[i] == maxCnt) {
			if (modeCnt > 1) {
				--modeCnt;
				continue;
			}
			if (modeCnt == 1) {
				mode = i - NBASE;
				break;
			}
		}
	}

	mSort(0, N - 1);

	printf("%d\n", round(sum / N));
	printf("%d\n", a[N / 2]);
	printf("%d\n", mode);
	printf("%d\n", a[N - 1] - a[0]);

	return 0;
}