백준 알고리즘 2108번: 통계학 [C++] (카운팅 정렬)

문제 출처: www.acmicpc.net/problem/2108

2108번: 통계학

아래 내용은 재채점되어 틀린 풀이가 되었습니다.(2022년 12월 21일 데이터 추가 이후)

데이터 추가 이후 재채점 결과

수정된 풀이 방법: https://travelerfootprint.tistory.com/259

백준 알고리즘 2108번: 통계학(자바 Java)

1. 코드

#include <iostream>
#include <cmath>

using namespace std;

int main(void)
{
	int arr[8002] = { 0, };
	int n, mid, input, hight = 0, alway;
	double avg = 0;

	cin >> n;        //n: 데이터 입력 횟수

	for (int i = 0; i < n; i++)
	{
		cin >> input;            //input: 데이터 입력값
		arr[4000 + input]++;     //카운팅 정렬 실행

		avg += input;            //avg: 평균값

		if (hight < arr[4000 + input])        //입력 중 최대 빈도 확인
		{
			hight = arr[4000 + input];        //hight: 빈도의 최댓값
			alway = input;                    //alway: 최대의 빈도를 차지하는 수
		}
	}
	int min, max;                 //max: 최댓값, min: 최솟값
	min = max = input;

	bool flag = false;            //mid값을 초기화를 했는지 확인 용도
	int cnt = 0;                  //최대의 빈도를 가진 수의 갯수 확인 용도
	int sum = 0;                  //입력된 횟수 확인 용도

	for (int i = 0; i < 8002; i++)
	{
		int value = i - 4000;
		if (arr[i] > 0)
		{
			sum += arr[i];
			if (sum >= n / 2 + 1 && !flag)
			{
				mid = value;
				flag = true;
			}
			if (min > value) min = value;
			if (max < value) max = value;

			if (arr[i] == hight) cnt++;
			if (cnt == 2)        //두 번째로 작은 수만
			{
				cnt = 3;
				alway = value;
			}
		}
	}

	cout << round(avg / n) << "\n" << mid << "\n" << alway << "\n" << max - min;
	return 0;
}

(실행)

2. 풀이

이 문제는 카운팅 정렬을 써서 하면 더 편하게 할 수 있을 것 같다는 생각에 카운팅 정렬을 활용하여 풀어보았다.

#include <iostream>
#include <cmath>

기존에 iostream을 쓰는데 추가적으로 cmath도 포함시켜줍니다. 왜냐하면 문제 중 반올림을 해야 하는데 직접 계산을 할 수는 있지만 함수로 표현하면 더 깔끔해서 함수를 활용하기 위해 cmath 헤더 파일도 포함한다.

int arr[8002] = { 0, };

카운팅 정렬을 할 배열인데 선언 크기가 8002인 이유는 입력되는 값이 절댓값 4000이라고 한다. 그렇다면 입력 범위가 -4000~4000인데 거기에 0 또한 입력될 수 있기 때문에 총 8001개를 입력받을 수 있도록 한 것이다.

int arr[8002] = { 0, };
int n, mid, input, hight = 0, alway;
double avg = 0;

cin >> n;        //데이터 입력 횟수

문제 해결에 필요한 변수들을 선언하고 사용자에게 입력 횟수를 변수 n을 통해 입력받는다.

for (int i = 0; i < n; i++)
{
    cin >> input;            //input: 데이터 입력값
    arr[4000 + input]++;     //카운팅 정렬

    avg += input;            //avg: 평균값

    if (hight < arr[4000 + input])        //입력 중 최대 빈도 확인
    {
        hight = arr[4000 + input];        //hight: 빈도의 최댓값
        alway = input;                    //alway: 최대의 빈도를 차지하는 수
    }
}

n만큼 input으로 데이터를 입력받는데 input에 4000을 더한 인덱스 값을 증가시켜 카운팅 정렬을 한다. 그리고 avg은 평균값이기 때문에 input입력 후 avg에 값을 더해준다. 그리고 hight를 통해서 제일 많은 빈도를 가진 수와 빈도 횟수를 확인하고 빈도 횟수를 큰 값으로 hight를 초기화하고 alway에는 최대 빈도 횟수를 차지하는 수를 대입한다.

int min, max;         //max: 최댓값, min: 최솟값
min = max = input; 

min과 max를 선언 후 마지막에 입력된 input값으로 초기화를 시켜준다.

bool flag = false;            //mid값을 초기화를 했는지 확인 용도
int cnt = 0;                  //최대의 빈도를 가진 수의 갯수 확인 용도
int sum = 0;                  //입력된 횟수 확인 용도

그리고 각 용도에 맞는 변수들을 선언과 동시에 초기화를 시킨다.

for (int i = 0; i < 8002; i++)
{
	int value = i - 4000;
	if (arr[i] > 0)
	{
		sum += arr[i];
		if (sum >= n / 2 + 1 && !flag)
		{
			mid = value;
			flag = true;
		}
		if (min > value) min = value;
		if (max < value) max = value;

		if (arr[i] == hight) cnt++;
		if (cnt == 2)        //두 번째로 작은 수만
		{
			cnt = 3;
			alway = value;
		}
	}
}

value 값으로 i - 4000을 한 이유는 데이터를 입력 후 배열을 이용하여 카운팅 정렬을 진행할 때 4000을 더했기 때문에 다시 빼주는 것이다. 그리고 배열의 값이 0보다 크다는 것은 1번이라도 입력되었다는 것이다.

그리고 sum을 이용하여 반도의 횟수를 더한다. 그래서 그 값이 n / 2 + 1보다 크거나 같으면 mid값을 value로 초기화를 해주는데 이때 mid값은 한 번만 입력하면 되기 때문에 flag를 이용하여 flag값이 참이라면 mid를 다시 초기화를 진행하지 않는다.

그리고 min값과 value값을 비교하여 더 작은 것을 min으로 초기화를 하고 max도 마찬가지로 더 큰 값을 초기화해준다. 마지막으로 위에서 가장 큰 빈도 횟수를 hight라는 변수에 저장했는데 그 값을 이용하여 가장 큰 빈도의 횟수가 여러 개가 있는지 확인해준다. 만약 2개가 있다면 alway값을 value로 초기화시켜준다. 그리고 alway는 가장 큰 빈도의 수가 여러 개가 있으면 두 번째로 작은 것으로 해야 하기 때문에 alway는 cnt가 2일 때만 초기화를 진행시켜주고 다시 접근할 필요가 없기 때문에 cnt의 값을 3으로 초기화시킨다.

cout << round(avg / n) << "\n" << mid << "\n" << alway << "\n" << max - min;

avg에는 n만큼의 input값들의 합이 저장되어있어서 n으로 나눈 뒤 round 함수를 통해서 반올림을 해준다. 그리고 mid값과 alway값을 출력한 뒤 input의 최댓값인 max와 최솟값인 min을 빼서 input의 범위를 출력해준다.

3. 느낀 점

단순하게 정렬만 하면 해결될 줄 알았는데 생각보다 많은 여러 가지 요소들을 고려해야 해서 조금 힘들었지만 다양한 반례들을 대입해보면서 해결하였지만 다음에는 설계를 잘해야겠다.