2108번 통계학(C)

어렵다. 통계라서 대충 끄적이고 금방 끝내려고 했는데 최빈값 도출하는게 이 문제의 핵심인 것 같다.

이 문제를 통해서 애매하게 알고 있던 개념들도 다시 한 번 확인해 볼 수 있었기에 뭐...시간은 꽤 날렸지만 괜찮...다 

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

2108번: 통계학

문제

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

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값 (이 문제의 경우,소수점 이하 첫째 자리에서 반올림한 값을 출력한다.)
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값 (이 문제의 경우,여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.)
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

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

사전지식

문제를 풀면서 알게 된 사실

1. break문은 if문을 빠져나가는 것이 목표가 아니라, '반복문'을 빠져나가는 것이 목표라는 사실. 즉 for문 안에 이중if문이 있고, 그 안에 break가 있는 경우, 바로 for문을 빠져나올 수 있다. 억지로 goto문을 쓰면서 문법을 깨뜨릴 필요가 없다는 것이다.

2. %0.f는 소수점 이하 첫째 자리에서 반올림한 값을 출력한다. %.1f %.2f도 마찬가지였던 것이고, 알아서 반올림으로 처리를 해 주는 것 같다.

3. 선택 정렬, 버블 정렬, 삽입 정렬은 시간복잡도가 O(n2)이고, 퀵 정렬은 시간복잡도가 O(n x logn)이기 때문에 웬만하면 퀵 정렬을 사용하는 것이 여러모로 시간 초과를 방지할 수 있겠다.

해결과정

산술평균은 그냥 평균내고 %.0f로 반올림만 잘 처리해주면 되고, 중앙값은 퀵 정렬 후 가운데 값 출력하면 되고, 범위는 퀵 정렬된 맨 끝 값에서 맨 처음 값의 차를 출력하면 되었다.

문제는 최빈값이다... 최빈값이 2개 이상일 경우 2번째로 작은 값을 출력하라니 너무 어려운 조건이었다. 최빈값은 이 분의 도움을 받아서 성공시켰다...

https://mjeong9316.tistory.com/172

[C 언어] 백준 2108. 통계학

이 분의 아이디어를 간단히 정리하면, 숫자가 등장한 빈도수를 나타내는 배열을 이용하는 것인데, 숫자에 음수도 있기 때문에 이를 고려하여 -4000이 아닌 0으로 입력될 수 있도록 arr[n+4000]으로 먼저 처리를 해준다.

그 다음에 최빈값을 찾는데, 최빈값이 유일할 경우 그 값을 출력한다. 최빈값이 여러 개일 경우, 가장 작은 최빈값은 통과하고 두 번째로 작은 최빈값을 출력하도록 조치를 취한다. 예를 들어 최빈값이 32와 35가 공동일 경우, 32는 flag값을 0으로 만들어 다시 반복문을 수행하고, 35 차례가 왔을 시 flag값이 0인 조건에 맞아떨어져 35가 출력된다.

코드

#include <stdio.h>
#include <stdlib.h>
int num[500000];
int freq[8001];

int maxFinder(int* arr, int size_arr) {
	int maxV = arr[0];
	for (int t = 0; t < size_arr; t++) {
		if (maxV < arr[t]) maxV = arr[t];
	}
	return maxV;
}
int compare(const void* a, const void* b) {
	int n1 = *(int*)a;
	int n2 = *(int*)b;
	if (n1 < n2) return -1;
	else if (n1 > n2) return 1;
	else return 0;
}

int main() {
	int N, i, j;
	int max;
	int mode;
	int sum = 0, flags = 0;

	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &num[i]);
		sum += num[i];
		freq[num[i] + 4000]++;
	}
	qsort(num, N, sizeof(int), compare);
	
	max = maxFinder(freq, 8001);
	for (i = 0; i < 8001; i++) {
		if (max == freq[i]) flags++;
	}
	for (i = 0; i < 8001; i++) {
		if (flags == 1) {
			if (max == freq[i]) {
				mode = i - 4000;
				break;
			}
		}
		else {
			if (max == freq[i])
				if (flags == 0) {
					mode = i - 4000;
					break;
				}
				else flags = 0;
		}
}

	printf("%.0f\n", (sum / (double)N));
	printf("%d\n", num[N / 2]);
	printf("%d\n", mode);
	printf("%d\n", num[N - 1] - num[0]);
	return 0;
}

결과

Class 2 뱃지를 얻었는데 1이 더 예쁜 것 같은 느낌