[백준] 2108번 : 통계학 (C언어 / C99)

문제

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

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

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

 

 

조건 및 입출력

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

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

- 시간 제한: 2초 이내 / 메모리 제한: 256MB 이내

 

 

코드 (C99)

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

//전역변수 선언부
int num[500000] = { 0 };

//프로토타입 선언부
long long average(int num[], int data);
int mid_value(int num[], int data);
int range(int num[], int data);
int popular(int num[], int data);
void heap_sort(int num[], int data);

main()
{
	int data;
	scanf("%d", &data);

	for (int i = 0; i < data; i++)
		scanf("%d", &num[i]);
	
	heap_sort(num, data);

	printf("%lld\n", average(num, data));
	printf("%d\n", mid_value(num, data));
	printf("%d\n", popular(num, data));
	printf("%d\n", range(num, data));

	return 0;
}

void heap_sort(int num[], int data)
{
	for (int i = 1; i < data; i++)
	{
		int child = i;
		do
		{
			int root = (child - 1) / 2;
			if (num[root] < num[child])
			{
				int temp = num[root];
				num[root] = num[child];
				num[child] = temp;
			}
			child = root;
		} while (child != 0);
	}
	
	for (int i = data - 1; i >= 0; i--)
	{
		int temp = num[0];
		num[0] = num[i];
		num[i] = temp;
		int root = 0;
		int child = 1;
		do
		{
			child = 2 * root + 1;

			if (child < i - 1 && num[child] < num[child + 1])
				child++;
			if (child < i && num[root] < num[child])
			{
				temp = num[root];
				num[root] = num[child];
				num[child] = temp;
			}
			root = child;
		} while (child < i);
	}
}

int popular(int num[], int data)
{
	int arr[8001] = { 0 };
	int index, max = 0, count = 0;

	for (int i = 0; i < data; i++)
	{
		index = num[i] + 4000;
		arr[index]++;

		if (arr[index] > max)
			max = arr[index];
	}

	index = 0;

	for (int i = 0; i < 8001; i++)
	{
		if (arr[i] == 0)
			continue;

		if (arr[i] == max)
		{
			if (count == 0)
			{
				index = i;
				count++;
			}
			else if (count == 1)
			{
				index = i;
				break;
			}
		}
	}
	return index - 4000;
}

int range(int num[], int data)
{
	return abs(num[data - 1] - num[0]);
}

int mid_value(int num[], int data)
{
	int pivot = data / 2;

	return num[pivot];
}

long long average(int num[],int data)
{
	double result = 0.0;

	for (int i = 0; i < data; i++)
		result += num[i];
	
	return round(result / data);
}

 

 

---

여담

쉬운 문제라고 생각했다.

최빈값을 구현하기 전까지는 말이다.

 

정렬 문제이므로 정렬을 하지 않으면 시간 제한에 걸릴 것 같았고, 정렬을 하고 데이터를 처리하는 것이 쉽게 문제를 풀 수 있을 것이라 생각했다. 나는 힙정렬(heap sort)를 이용하여 데이터를 정렬 한 뒤 데이터를 처리하고자 했다.

그렇게 산술평균, 중앙값, 범위는 금방 구현했다.

 

1. 산술평균

-> 산술평균 같은 경우, 우리가 일상생활에서 평균을 구하는 방식과 동일하게 구하면 된다. 원소를 전부 더하고 원소의 개수를 나눈 값을 반올림 해서 정수 형태로 반환하면 된다.

 

2. 중앙값

-> 데이터값은 항상 홀수개가 주어짐이 보장되므로, 데이터의 개수 /2를 해주면 된다.

C에서는 배열 인덱스가 0번부터 시작이고 정수값을 나눠주면 소수점 이하는 버림하기 때문에 데이터의 개수 /2에 있는 인덱스 값을 반환해 주면 된다.

 

3. 범위

-> 0번 인덱스와 마지막 인덱스의 값의 절대값을 반환해주면 된다. (차이를 구하라고 했으므로)

 

4. 최빈값

최빈값을 구하는데 오랜 시간이 걸렸다.

최빈값을 어떻게 구현할지 2~3시간 동안 앉아서 생각했다. 각종 플래그도 세워가며 구현했지만 결국 스파게티 코드가 되었고, 각각의 경우에 대해 플래그의 플래그의 플래그를 세우다 보니 코드가 복잡해지고 모든 경우에 대해 플래그를 세우다보니 하니 일반화도 되지 않고 경우에 따라 답이 틀리게 나왔다.

 

도져히 어떻게 구현할지 감이 안잡혀서 결국 다른 분들의 풀이를 보며 도움을 받았다.

나는 아래의 블로그에서 도움을 받았다.

https://sedangdang.tistory.com/19

[C] 백준 | 2108번 코드 - *통계학

 

이 분이 정말 깔끔하게 잘 정리를 해두었다.

 

요약을 하자면, 입력 조건에서 '입력되는 정수의 절댓값은 4,000을 넘지 않는다'를 이용하는 것이다.

절댓값이 4,000을 넘지 않는다는 것은, 주어지는 데이터의 값이 -4,000 ~ 4,000이라는 것이다.

 

때문에 8001개의 값을 저장할 수 있는 배열을 만든다. (범위 -4,0000 ~ 4,000; 0포함) -

 

그렇게 입력된 데이터를 하나씩 읽어들이면서, 빈도수를 체크한다.

예를 들어, -4000이 들어있는 값을 읽으면 0번 인덱스에 +1을 해주고,

0이 들어있는 값을 읽으면 4000번 인덱스에서 +1을 해주는 것이 되겠다.

마찬가지로 4000의 값이 들어오면 8000번 인덱스에 +1이 될 것이다.

 

그렇다면 3875가 들어오면 몇 번 인덱스에 값이 저장되겠는가? 7875번에 값이 저장되겠다. 

 

그렇게 빈도수 1차 체크를 마친다.

1차 체크가 끝나면 가장 최빈값을 찾을 수 있다.

 

그 후 2차 체크를 한다.

출력 초건에 '출력값이 여러개 있는 경우 2번째로 작은 값을 출력해야 한다'는 조건이 있으므로 플래그를 만들어서 이를 체크해 주면 된다.

 

그렇게 여러개의 값이 있는 경우 count 플래그를 만들어서 2번 째로 큰 값을 반환한다.

또는 여러개 있지 않는 경우는 for문을 다 돌고 값을 반환한다.

 

값을 반환할 때는, -4000을 해 줘야 한다.(처음 인덱스에 +4000을 했으므로 보정해줘야 한다.)

 

---

아이고 어렵다...

오전 시간은 이 문제 푼다고 시간이 다 갔다.

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 댓글 남겨주세요 ! + 더 좋은 풀이 방법이 있다면 알려주세요 :)