백준2108 통계학 - C언어

 

1. 문제의 접근

수가 최대 500,000개 주어지고, 각 정수의 절대값은 4,000을 넘지 않기 때문에 최대의 경우로 계산해도 20억이 가능하므로 배열은 Integer type으로 만든다.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define INF 987654321
struct st {
	int tag;
	int fre;
}Fre[4000 + 4000 + 1] = { {0,0} };

하지만 여기서 일반 배열로 선언하기보다 최빈값을 구하기 위해서 숫자와 빈도를 기록하는 구조체를 선언한다.

tag 는 해당 구조체가 저장하는 숫자이고, fre 는 몇 번 나왔는지 기록하기 위한 수이다.

배열의 개수 4000+4000+1은 정수의 절대값이 4000이 넘지 않기 때문에 -4000~-1, 1~4000 개의 수와 0을 포함한 1이다.

 

2. 문제의 입력

그 후 입력을 받는다.

int N;
int Su = 0;//총 몇 개의 수를 고려해야 하는지 셈
	
for (int i = 0; i < 8001; i++) {
		Fre[i].tag = -INF;
		Fre[i].fre = -INF;
	}
	scanf("%d", &N);
	// 입력값이 -4000 ~4000 까지 이므로 -4000 을 기준을0으로 잡고 저장
	int sum = 0;
	for (int i = 0; i < N; i++) {
		int a;
		scanf("%d", &a);
		Fre[a + 4000].tag = a;
		if (Fre[a + 4000].fre < 0) {
			Fre[a + 4000].fre = 1;
		}
		else {
			Fre[a + 4000].fre += 1;
			Su--;
		}
		sum += a;
		Su++;

	}

입력을 받을때 배열에는 음수 index가 없으므로 -4000을 0을 offset으로 정수를 저장한다. 

예를 들어 -4000이 들어오면 Fre[0] 에 저장하고, 4000이 들어오면 Fre[8000]에 저장하는 식이다.

 

그리고 최빈값을 구할때 Fre[i].fre 를 기준으로 내림차순으로 정렬할 것이기 때문에 모두 -INF 로 채워 해당 배열에 숫자가 입력되지 않는 경우를 뒤로 보낼 것이다. tag도 마찬가지이다.

입력을 받으면서 -INF일 경우 fre를 1로 올려주고, 이미 1 이상이라면 해당 수가 들어올때마다 +1씩 해준다.

Su 는, 그래서 총 몇 가지 종류의 정수가 들어왔는지를 알기 위해 계산하는 변수이고, 이미 있는 숫자가 또 들어오는 경우는 세지 않는다.

예를 들어 1,2,1,2,1 이 들어왔다면 Su는 2가 된다.

 

3. 문제해결을 위한 계산 

 

그 다음 숫자가 들어올때마다 계산한 sum 값으로 평균값을 계산한다. 

문제에서 첫 번째 소수점에서 반올림하라 했으므로 <math.h>의 round 함수를 이용해 (double)sum/N을 더블 타입으로 캐스팅한 후 반올림하여 산술평균을 구한다.

이 때 그냥 sum/N는 int 타입으므로 항상 소수점을 버리므로 주의해야한다.

숫자의 범위는 정렬하고 나서 가장 큰 수와 가장 작은 수를 빼주면 나온다.

예를 들어 2와 7이면 범위는 5개가 된다.

또한 Fre[Su-1]을 하는 이유는 Su 가 총 5개면 배열의 index는 4이기 때문이다.

	// 평균값 구하기//
    double avg =round( (double)sum / N);
    //숫자 기준 내림차순으로 정렬//
	qsort(Fre, 8001, sizeof(struct st), cmp_tag_lower);
    // 중간값 구하기//
	int Median = 0;
	int tmp_idx = 0;
	for (int i = 0; i < Su; i++) {
		tmp_idx += Fre[i].fre;
		if (tmp_idx-1 >= N / 2 ) {
			Median = Fre[i].tag;
			break;
		}
	}
    // 범위 구하기 //
	int Range = Fre[0].tag - Fre[Su - 1].tag;

그 후 <stdlib.h>의 qsort 함수를 이용해 정렬한다.

N^2의 정렬방법을 경우 8천개를 정렬해야하므로 타임아웃이 곧잘 난다. 

그러므로 로그 스케일의 qsort를 써서 정렬한다. 형식은 다음과 같다.

qsort(배열의 시작 포인터, 자료의 개수, 자료 하나의 크기, 비교 함수)

 

Fre를 정렬하고 싶으므로 시작 지점인 Fre를, 총 8001개를 정렬해야하고, 그 하나의 크기는 struct st의 크기이다. 

비교함수는 콜백함수로 함수를 불러와서 쓸 수 있다.

// 내림차순정렬 빈도기준
int cmp_number_lower(void* p, void* q) {
	struct st* a=p, * b=q;
	if (a->fre < b->fre) return 1;
	else if (a->fre == b->fre) return 0;
	return -1;
}
// 내림차순정렬 숫자기준
int cmp_tag_lower(void * p, void * q) {
	struct st* a=p, * b=q;
	if (a->tag < b->tag) return 1;
	else if (a->tag == b->tag) return 0;
	return -1;
}

형식은 p 와 q를 비교하는 것을 기준으로, 정렬 조건은 결과가 1이 될 때이다.

어떤 형식의 포인터값을 argument로 줄지 모르므로 void pointer 로 선언한다.

그 후 void pointer 를 내가 아는 pointer 형식으로 바꿔준다. 여기선 struct st pointer type 으로 변경한다.

그리고 내림차순으로 정렬할 것이므로, 뒤에 있는 값이(q) 앞에 값(p) 보다 클 경우 바꿔준다.

같으면 0 작으면 -1을 return 해 내림차순으로 만들 비교함수를 만들어 줄 수 있다. 

cmp_number_lower 는 Fre[i].fre 를 기준으로 빈도가 많은 순서대로 정렬한다.

cmp_tag_lower 는 Fre[i].tag 를 기준으로 숫자가 큰 순서대로 정렬한다.

 

Median 은 중간의 값이고 N은 항상 홀수이므로 중간값의 위치는 값을 기준으로 정렬했을 때 N/2가 될 것이다.

예를 들어 N이 5개면 N/2는 2가 되므로 idx와 맞게 된다.

하지만 우리는 배열로 입력 숫자 하나하나를 저장한게 아니기 때문에 앞에서 부터 접근하여 숫자가 총 몇 개 나왔는지 파악해야한다.

그렇기 위해서 fre를 세어 그 수가 N/2와 같아지거나 그것보다 막 커졌을 경우가 중간값이 위치한 곳이 된다.

하지만 숫자와 idx는 1차이가 나므로 수에서 1을 빼서 맞춰준다.

예를 들어, 1,1,2,2,3 일 경우 N/2는 2가 된다. 1이 2개이므로 tmp_idx는 1을 지날 때 2가 되고 아직 3이 아니므로 2의 fre를 더하면 tmp_idx = 4 가 되므로 3보다 커지기 때문에 2가 median 값을 가지고 있는 것이다.

 

그 후 최빈값을 구하기 위해 다시 배열을 빈도 기준으로 내림차순 정렬한다.

 

문제에서, 최빈값이 여러개일 경우 2번째로 작은 수를 출력하라 했으니 다시 수를 기준으로 정렬해서 봐야한다.

(왜 이렇게 빙빙빙빙 돌려서 풀었을까? 머리 아파서 다른방법은 생각안했다)

 

빈도 기준으로 내림차순 정렬을 했다면 최빈값과 같은 빈도를 가진 수들을 뽑아 index를 어디까지 봐야할지 구한후 z에 저장한다.

 

그 후 최빈값을 가진 수들만 정렬을 한 후 만약 최빈값에 해당하는 수가 하나라면 0번째를 저장,

여러개라면 끝에서 2번째를 저장한다.

 

그리고 구한 모든 수를 출력하면 종료하게 된다.

	//빈도 기준 내림차순 정렬//
    qsort(Fre, 8001 , sizeof(struct st), cmp_number_lower);
	//최빈값끼리 정렬하기 위해 최빈값의 index 파악//
	int z = 0;
	for (int i=1; i<Su; i++){
		if (Fre[i].fre == Fre[0].fre) z = i;
		else {
			break;
		}
	}
	//최빈값끼리 정렬//
	qsort(Fre, z + 1, sizeof(struct st), cmp_tag_lower);
	int MFN; //최빈값
	if (z == 0) MFN = Fre[0].tag;
	else MFN= Fre[z - 1].tag;
	
	printf("%.f\n%d\n%d\n%d", avg, Median, MFN, Range);
	return 0;

---

C언어로 문제를 풀려다보니 하나하나 구현해야해서 힘이 든 것 같다.

하지만 탄탄하게 쌓아가다보면, 나중에 다른 언어로 시도해도 논리적으로는 막힘 없이 쉽게 할 수 있지 않을까 기대한다.

 

총 합친 코드는 다음과 같다.

 

#if 1
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define INF 987654321
struct st {
	int tag;
	int fre;
}Fre[4000 + 4000 + 1] = { {0,0} };

//내림차순정렬 빈도기준
int cmp_number_lower(void* p, void* q) {
	struct st* a=p, * b=q;
	if (a->fre < b->fre) return 1;
	else if (a->fre == b->fre) return 0;
	return -1;
}

// 내림차순정렬 숫자기준
int cmp_tag_lower(void * p, void * q) {
	struct st* a=p, * b=q;
	if (a->tag < b->tag) return 1;
	else if (a->tag == b->tag) return 0;
	return -1;
}

int main() {
	int N;
	int Su = 0;//총 몇개의 수를 고려해야 하는지 계산d
	for (int i = 0; i < 8001; i++) {
		Fre[i].tag = -INF;
		Fre[i].fre = -INF;
	}
	scanf("%d", &N);
	// 숫자와 그 숫자가 얼마나 자주 등장하는지를 struct에 저장
	// 이 때 입력값이 -4000 ~4000 까지 이므로 -4000 을 기준을0으로 잡고 저장
	int sum = 0;
	for (int i = 0; i < N; i++) {
		int a;
		scanf("%d", &a);
		Fre[a + 4000].tag = a;
		if (Fre[a + 4000].fre < 0) {
			Fre[a + 4000].fre = 1;
		}
		else {
			Fre[a + 4000].fre += 1;
			Su--;
		}
		sum += a;
		Su++;

	}
	double avg =round( (double)sum / N);
	// 중앙값과 범위 계산하기 위한 값 내림차순 정렬 
	qsort(Fre, 8001, sizeof(struct st), cmp_tag_lower);

	int Median = 0;
	int tmp_idx = 0;
	for (int i = 0; i < Su; i++) {
		tmp_idx += Fre[i].fre;
		if (tmp_idx >= N / 2 + 1) {
			Median = Fre[i].tag;
			break;
		}
	}
	int Range = Fre[0].tag - Fre[Su - 1].tag;

	qsort(Fre, 8001 , sizeof(struct st), cmp_number_lower);
	
    //최빈값끼리 정렬
	int z = 0;
	for (int i=1; i<Su; i++){
		if (Fre[i].fre == Fre[0].fre) z = i;
		else {
			break;
		}
	}

	qsort(Fre, z + 1, sizeof(struct st), cmp_tag_lower);
	int MFN;
	if (z == 0) MFN = Fre[0].tag;
	else MFN= Fre[z - 1].tag;
	
	printf("%.f\n%d\n%d\n%d", avg, Median, MFN, Range);
	return 0;
}



#endif