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

---

2108. 통계학 (누르면 해당 문제로 이동)

정렬을 활용하는 문제

 

제약사항)

시간 : 2 초

메모리 : 256 MB

 

문제)

수를 처리하는 것은 통계학에서 상당히 중요한 일이다.

통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

 

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값

2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값

3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값

4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

 

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

 

입력)

첫째 줄에 수의 개수 N(1<=N<=500,000) 이 주어진다.

그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

 

출력)

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

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

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

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

 

입출력 예제

입력	출력
5 1 3 8 -2 2	2 2 1 10
1 4000	4000 4000 4000 0
5 -1 -2 -3 -1 -2	-2 -2 -1 2

 

---

 

풀이 순서)

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

  - 산술 평균을 구하기 위해 입력되는 수들의 합을 구합니다. (sum)

  - sum을 int 형으로 선언해주었기 때문에 산술평균을 구할 때 형 변환을 해주어야 합니다. ( (double)sum/N )

  - "%.nf" : 소수점 이하 n번째 자리까지 표시하도록 한다는 의미로,

    이 문제에서는 소수점 이하 첫째 자리에서 반올림하라고 지시했으므로 "%.0f" 형태를 이용해 값을 출력합니다.

 

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

  - 중앙값을 구하기 위해 먼저 입력된 수들을 정렬해야 하므로 qsort 함수를 사용해 오름차순으로 정렬했습니다.

  - 문제에서 N(숫자의 개수)이 홀수라고 가정했으므로, 중앙값은 정렬한 수에서 (N+1)/2 번째 값이 됩니다.

  - 이 때, 배열은 0번째 부터 시작하기 때문에 (N+1)/2-1 번째 값을 출력합니다.

 

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

  - 최빈값을 구하기 위해 각 숫자가 나온 횟수를 세기 위한 변수 cnt 배열을 사용했습니다.

  - 문제에서 입력되는 수의 절댓값은 4,000을 넘지 않는다고 했으므로 입력된수+4000을 배열의 인덱스 번호로 사용합니다.

     ex) num = 1 -> cnt[4001]++ / num = 10 -> cnt[4010]++ / num = -1 -> cnt[3999]++ 와 같이 증가됩니다.

  - 최빈값이 여러개일 경우 두 번째로 작은 값을 출력해야 하므로, cnt 배열의 최댓값을 찾고,

    이 최댓값이 몇 번 나왔는지 알기 위해 flags 변수를 사용합니다.

  - flags=1 일 경우 최댓값과 같은 값을 갖는 cnt의 인덱스를 찾아 출력합니다.

    (이 때, i+4000에 값을 저장했으므로, i-4000을 출력합니다.)

  - flags>2 일 경우 최빈값이 여러 개인 경우이므로, -4000(인덱스 0) 부터 시작하여 최댓값과 같은 값을 갖는 cnt의 인덱스를 찾고,

    첫 최빈값일 경우 flags 값을 0으로 바꾼 후 넘어갑니다.

    그 다음 최빈값일 경우(flags=0일 경우) 그 때의 인덱스 값을 출력합니다.

 

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

  - 수를 입력 받을 때, 최댓값과 최솟값을 찾아 그 차이를 구해주면 됩니다.

 

---

 

소스코드 및 결과 (C)

#include <stdio.h>
#include <stdlib.h>

int num[500001] = { 0, };
int cnt[8001] = { 0, };

int compare(const void *a, const void *b) {		// qsort 오름차순 정렬 위한 함수
	if (*(int *)a > *(int *)b)
		return 1;
	else if (*(int *)a < *(int *)b)
		return -1;
	else
		return 0;
}

int maxFinder(int *arr, int size_arr) {		// 배열에서 최댓값 찾는 함수
	int maxV = arr[0];
	for (int i = 0; i < size_arr; i++)
		if (maxV < arr[i])
			maxV = arr[i];

	return maxV;
}

int main() {
	int N, sum = 0, flags = 0;
	int min = 4000, max = -4000;
	int mode = 0;

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &num[i]);
		sum += num[i];			// 산술평균을 구하기 위해 모든 값의 합을 구함

		if (min > num[i])		// 범위를 구하기 위해 최대, 최솟값을 구함
			min = num[i];
		if (max < num[i])
			max = num[i];

		cnt[num[i] + 4000]++;	// 최빈값을 찾기 위해 각 숫자가 몇 번 나왔는지 세기 위한 변수
	}

	for (int i = 0; i < 8001; i++)				// 최빈값 구하는 부분
		if (maxFinder(cnt, 8001) == cnt[i])
			flags++;

	for (int i = 0; i < 8001; i++) {
		if (flags == 1) {
			if (maxFinder(cnt, 8001) == cnt[i]) {
				mode = i - 4000;
				break;
			}
		}
		else {
			if (maxFinder(cnt, 8001) == cnt[i]) {
				if (flags == 0) {
					mode = i - 4000;
					break;
				}
				else
					flags = 0;
			}
		}
	}

	qsort(num, N, sizeof(int), compare);	// 중앙값을 구하기 위해 qsort 정렬을 사용함

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

	return 0;
}

 

메모리 : 5052 KB

시간 : 192 ms

코드길이 : 1223 B

 

 

---