BOJ - 2108 통계학 해결 전략 (C++)

• 문제

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

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

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

• 입력

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

• 출력

1. 첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.
2. 둘째 줄에는 중앙값을 출력한다.
3. 셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
4. 넷째 줄에는 범위를 출력한다.

• 예제 입력 1
  5
  1
  3
  8
  -2
  2
• 예제 출력 1
  2
  2
  1
  10

해결 전략

  조금만 생각해보면 어렵지 않게 해결할 수 있다. 수의 범위에 주목하라. -4000 ~ 4000이다. 즉, 입력 가능 정수의 개수를 고려하면, 이 문제는 곧 '비둘기집의 원리'에 기반해 '정수 값에 대한 배열'을 만들어주면 된다. 즉, 크기가 8001인 배열(8000도 상관은 없지만, 8001이 보다 더 직관적)을 만들면 된다.
(물론, 이를 비둘기집의 원리라고 생각할 필요도 없다.)

  물론, 정수 50만개에 대한 벡터나 배열로서 문제를 다룰 수도 있겠지만, 그렇게 하면 재앙이 시작될 것이다. 분명 이 방식이 가장 직관적이다. 물론, 이렇게 하면 algorithm 헤더를 사용하기가 힘들지만, 어렵지 않게 평균, 중앙, 최빈, 범위를 구하는 반복문을 구축할 수 있다.

  이때, 한 가지 주목할만한 C언어의 기초 개념이 있는데, 실수형 변수를 printf함수로 출력할 때 포맷문자 %f에 .을 더해 소수점 출력을 도모할 때에는 반올림이 된다는 사실이다. 이는 의외로 많은 프로그래머가 모르는 개념인데, 본 문제를 통해 이 역시 얻어갈 수 있을 것이다. 참고로, 내림이나 올림은 ceil, floor 함수를 사용하면 된다. 아마 본인의 기억상 math.h 헤더에 있을 것이다(아닐 수도 있음).

  더 이상의 자세한 설명은 생략한다.

입력 가능한 수의 개수보다 입력 가능한 값의 범위가 더 작으면, 값에 대한 배열을 만들어 접근하는 것이 더 편리할 확률이 높다.

  아래는 코드이다.

#include <iostream>
#include <stdio.h>
// BOJ - 2108 Statistics
using namespace std;

int number[8001];

int main(void) {
	int n, num, maximum, minimum, maxcnt = 0, maxcntnum, cntsum = 0, median;
	double sum = 0, avg;

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

	avg = sum / (double)n;
	if (avg > -0.5 && avg < 0) avg = -avg;	// 22년2월21일자 재채점 결과 업데이트
	printf("%.0f\n", avg);	// 산술평균

	for (int i = 0; i < 8001; i++) {
		if (number[i] > 0)
			cntsum += number[i];
		if (cntsum >= n / 2 + 1) {
			median = i - 4000;
			break;
		}
	}
	cout << median << endl;	// 중앙값

	for (int i = 0; i < 8001; i++) {
		if (number[i] > maxcnt) {
			maxcnt = number[i];
			maxcntnum = i - 4000;
		}
	}
	for (int i = maxcntnum + 4001; i < 8001; i++) {
		if (number[i] == maxcnt) {
			maxcntnum = i - 4000;
			break;
		}
	}
	cout << maxcntnum << endl;	// 최빈값

	for (int i = 8000; i >= 0; i--) {
		if (number[i] > 0) {
			maximum = i - 4000;
			break;
		}
	}
	for (int i = 0; i < 8001; i++) {
		if (number[i] > 0) {
			minimum = i - 4000;
			break;
		}
	}
	cout << maximum - minimum;	// 범위

	return 0;
}