(C++) [백준 2108번] 통계학

 

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

2108번: 통계학

 

 

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

   위의 4가지 조건에 맞게 답을 구하면 되는 문제이다.

 

N이 50만이고, 시간 제한이 2초니까 O(N)내에 해결하면 되는 문제라고 생각한다.

 

산술평균은 말 그대로 하면 되는데 double형을 쓰지 않는다면 형변환이 필요하고, 출력부에 소수점 이하 첫째 자리에서

반올림한 값을 출력한다. 라는 조건이 있으므로 round같은 함수를 이용해서 반올림해줄 필요가 있다.

int Cal()
{
	double res = 0;
	for (int i = 0; i < n; i++)
		res += vec[i];
	return round(res /= (double)n);
}

중앙값은 나같은 경우 그냥 정렬해서 중앙값을 찾아줬다. 이 문제는 N의 개수가 항상 홀수라는 정의가 있으므로

0부터 시작하는 인덱스의 경우 항상 /2했을때 중앙값을 찾아줄 수 있다.

int Center()
{
	sort(vec.begin(), vec.end());
	return vec[n / 2];
}

최빈값이 가장 어려웠다. 최빈값은 여러가지 조건이 있는데, 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

라는 조건이 있고, 이 문제의 범위가 절대값이 4,000을 넘지 않는 정수 이므로 음수도 포함되기 때문이다.

int Count()
{
	int cnt = 0, max_Num = 0;
	for (int i = 0; i < n; i++)
	{
		countArr[(vec[i]+COMP)]++;
	}
	int max = 0;
	for (int i = 0; i < NUMBER; i++)
	{
		max = (max < countArr[i]) ? countArr[i] : max;
	}
	for (int i = 0; i < NUMBER; i++)
	{
		if (max == countArr[i]) {
				cnt++;
				max_Num = i - COMP;
		}
		if (cnt > 1)
			return (i - COMP);
	}

	return max_Num;
}

배열(벡터도 마찬가지)은 인덱스로 음수를 쓸 수 없어서, COMP라는 미리 정의된 4000짜리 정수를 이용해 보수처럼 계

산했다.

countArr는 카운팅 정렬 풀때처럼 생각해본건데, 어차피 범위는 -4000~+4000이므로 최대 8001까지의 배열 인덱스만

필요해서, 개수를 이용해서 최빈값을 찾아낼 수 있을것 같더라. (만약 4058과 7746의 값이 2라면 최빈값은 58과 3746인

식으로)

max는 이 배열에서의 최대 최빈값으로, 최빈값이 여러 개인 경우도 있을 수 있기 때문에 최대 최빈값이 필요하다고 생각했다.

NUMBER는 8005짜리 미리 정의된 상수인데, 카운팅 배열의 최대값이다.

첫번째 for (int i=0; i<NUMBER; i++) 반복문에서 최대 최빈값을 구하고, 두번째 반복문에서 최대 최빈값과 countArr[i]의

개수가 같다면 그 값을 저장해주고 cnt를 1 증가시킨다.

cnt를 1 증가시키는 이유는 최대 최빈값이 여러 개면 두 번째로 작은 수를 구해야 하기 때문이고, 값을 저장해주는 이유

는 최대 최빈값이 하나인 경우 그 값이 필요하기 때문이다.

 

만약 cnt가 2가 된다면 이 경우 최대 최빈값은 여러 개라는 뜻이 되는데, for가 0부터 돌고 있기 때문에(=작은 수부터 돌고 있기 때문에) cnt가 2가 됐을 때의 값이 두 번째로 작은 최빈값이고, 이 때는 바로 return해주면 된다.

 

만약 cnt가 1인 상태로 끝나는 경우 이 경우 최대 최빈값은 1개이므로 아까 저장했던 값을 return해주면 된다.

 

마지막으로 범위인데, 범위는 단순히 최대값 - 최소값을 해주면 된다.

이미 정렬됐다는 가정하에 아래처럼 쓸 수 있다.

int Range()
{
	return vec[n - 1] - vec[0];
}