4가지 통계값 찾기 문제를 다른방법으로 풀어보자

이전 포스팅에서 풀어보았던 4가지 통계값 찾기 문제를 다른 방법으로 풀어보자

첫번째 바꿔보고 싶은 것은 C언어에서 반올림 방법을 익힌 뒤 산술평균 문제에 적용하는 것이다.

반올림 대상 값으로 음수가 들어올 수 있음을 유의하자.

C언어에서 반올림 하는 방법

출력만 하는 경우는 아래와 같이 형식지정자를 쓰면 반올림이 된다.

float myFloat = 37.7777779f;
printf("%.2f", myFloat);
/// 출력 37.78

연산 등을 위해 반올림하는 경우 math.h를 사용한다.

#include <math.h>
float val = 37.777779f;
float rounded_down = floatf(val*100) / 100; /// 내림 37.77
float nearest = roundf(val*100) / 100; /// 반올림 37.78
float rounded_up = ceilf(val*100) / 100; /// 올림 37.78

몇 번째 자리에서 반올림 할 것인지에 따라 나눠주고 곱해주면 된다.

함수를 사용하는 것보다 사칙연산을 사용하는 것이 시간이 적게 걸리므로 이 부분은 수정 하지 않는 게 좋다고 결론냈다. 음수인 경우 양수와 반대로 -.5f 를 더해주는 것을 잊지말자.

두 번째로 고치고 싶은 것은 입력받은 숫자를 배열에 저장한 뒤 이 배열을 오름차순으로 정렬해서 중앙값을 찾는 것이다.

이를 위해 이용할 알고리즘은

Merge Sort
Heap Sort
Quick Sort

모두 정렬하지 않고 k 번째 값을 찾는

Quick Select
Medium of Medium

우선 Merge Sort 를 구현하여 중앙값을 찾아보자.

#include <stdio.h>
#include <string.h>

int FindMiddleValue(int* arr, int size);
void Merge(int* arr, int left, int middle, int right);

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

	int res_average = 0;
	float average_f = 0.f;
	int mediumIndx = cnt / 2;
	int bucket[8001] = { 0 };
	int max_value = -4001;
	int min_value = 40001;
	int range = 0;

	int* forMiddleArray = new int[cnt];

	for (int i = 0; i < cnt; i++)
	{
		scanf("%d", &inputNum);
		
		average_f += inputNum;

		bucket[inputNum + 4000]++;
		
		if (inputNum < min_value)
			min_value = inputNum;
		if (inputNum > max_value)
			max_value = inputNum;

		forMiddleArray[i] = inputNum;
	}

	/// 산술평균
	if (cnt != 0)
	{
		if (average_f < 0)
			res_average = average_f / cnt - 0.5f;
		else
			res_average = average_f / cnt + 0.5f;
	}
	printf("%d\n", res_average);

	/// 중앙값
	int middleValue = FindMiddleValue(forMiddleArray,cnt);
	printf("%d\n", middleValue);

	/// 최빈값
	int manyValue = -4001;
	int maxCnt = 0; int isEqual = 0;
	for (int i = 0; i < 8001; i++)
	{
		if (bucket[i] > maxCnt)
		{
			manyValue = i;
			maxCnt = bucket[i];
			isEqual = 0;
		}
		else if (bucket[i] == maxCnt)
			isEqual = 1;
	}
	int second = 0;
	if (isEqual)
	{
		for (int i = 0; i < 8001; i++)
		{
			if (bucket[i] == maxCnt)
				second++;
			if (second == 2)
			{
				printf("%d\n", i - 4000);
				break;
			}
		}
	}
	else if (isEqual == 0)
		printf("%d\n", manyValue - 4000);

	/// 범위
	range = max_value - min_value;
	printf("%d\n",range );

	delete[] forMiddleArray;
	return 0;
}


void MergeSort(int* arr, int left, int right)
{
	if (left >= right) return;

	int middle = (left + right) / 2;

	MergeSort(arr, left, middle);
	MergeSort(arr, middle + 1, right);

	Merge(arr, left, middle, right);
}

void Merge(int* arr, int left, int middle, int right)
{
	int sortedSize = right - left + 1;
	int* sortedArray = new int[sortedSize];
	int leftIndex = left, rightIndex = middle+1;
	int sortedIndex = 0;
	while (leftIndex <= middle && rightIndex <= right)
	{
		if (arr[leftIndex] < arr[rightIndex])
		{
			sortedArray[sortedIndex] = arr[leftIndex];
			leftIndex++;
		}
		else
		{
			sortedArray[sortedIndex] = arr[rightIndex];
			rightIndex++;
		}
		sortedIndex++;
	}
	while (leftIndex <= middle)
	{
		sortedArray[sortedIndex++] = arr[leftIndex++];
	}
	while (rightIndex <= right)
	{
		sortedArray[sortedIndex++] = arr[rightIndex++];
	}

	memcpy(&arr[left], sortedArray, sizeof(int)*sortedSize);

	delete[] sortedArray;
}


int FindMiddleValue(int* arr, int size)
{
	MergeSort(arr,0, size-1);
	return arr[size / 2];
}

속도가 더 느려지지만 MergeSort로도 충분히 해결할 수 있다.

다음은 Quick Select 를 구현해 활용해보자.

int partition(int* arr, int left, int right, int pivotIndex)
{
	swap(arr + pivotIndex, arr + right);
	int res_pivotIdx = right; int l = left;
	for(int i = left; i< right; i++)
	{
		if(arr[i] > arr[res_pivotIdx])
			continue;
		swap(arr+i, arr+l++);
	}

	swap(arr+l , arr+res_pivotIdx);
	res_pivotIdx = l;
	return res_pivotIdx;
}

int QuickSelect(int* arr, int left, int right, int k)
{
	int pivotIndex = right;
	pivotIndex = partition(arr, left, right, pivotIndex);

	if(k < pivotIndex)
		return QuickSelect(arr, left, pivotIndex-1, k);
	else if(k < pivotIndex +1 )
		return arr[pivotIndex];
	else
		return QuickSelect(arr, pivotIndex + 1, right, k);
}

int FindMiddleValue(int* arr, int size)
{
	return QuickSelect(arr, 0, size-1, size /2 );
}

QuickSelect 는 size 값만을 받아서 하는 방식으로 해결할 수도 있다.

int partition(int* arr, int size, int pivotIndex)
{
	int _pivotIndex = size-1;
	swap(arr+pivotIndex, arr+size-1);
	int l = 0;
	for(int i=0; i<size-1; i++)
	{
		if(arr[_pivotIndex] < arr[i]) continue;
		swap(arr+ i, arr+ l++);
	}
	swap(arr+l, arr+_pivotIndex);
	_pivotIndex = l;
	return _pivotIndex;
}

int QuickSelect(int* arr, int size, int k)
{
	int pivotIndex = size-1;
	pivotIndex = partition(arr, size, pivotIndex);

	if(k < pivotIndex)
		return QuickSelect(arr, pivotIndex, k);
	else if(k <pivotIndex+1)
		return arr[pivotIndex];
	else
		return QuickSelect(arr+pivotIndex+1, size-pivotIndex-1, k-pivotIndex-1);
}

int FindMiddleValue(int* arr, int size)
{
	return QuickSelect(arr, size, size/2);
}