⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️
https://www.acmicpc.net/problem/2108
2108번: 통계학
첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
www.acmicpc.net
Code
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
// qsort를 위한 compare함수
int compare(const void *a, const void *b) // 오름차순 비교 함수 구현
{
int num1 = *(int *)a; // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
int num2 = *(int *)b; // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
if (num1 < num2) // a가 b보다 작을 때는
return -1; // -1 반환
if (num1 > num2) // a가 b보다 클 때는
return 1; // 1 반환
return 0; // a와 b가 같을 때는 0 반환
}
int main() {
int num = 0; // 숫자 입력 횟수
int result[500000] = {0,}; // 입력받은 숫자를 저장하는 배열
int total = 0; // 산술평균 답
double remain = 0; // 산술평균을 위한 변수
int middle = 0; // 중앙값을 위한 변수
int boolean = 0; // 최댓값이 몇개 나왔는지 확인
int mode = 1; // 최대 등장한 숫자가 몇번 등장했는지 확인
int count[8001] = {0,}; // 등장 횟수를 기록
int result_mode = 0; // 최다 등장한 숫자
int range = 0; // 범위를 위한 변수
scanf(" %d", &num);
// 배열 입력 및 산술평균을 위한 총합, 최빈값 배열 구하기
for(int i = 0; i < num; i++){
scanf("%d", &result[i]);
count[result[i]+4000]++;
total += result[i];
}
// 계산의 편의성을 위한 정렬
qsort(result, num, sizeof(result[0]), compare);
//반올림을 위한 나머지 계산
remain = total % num;
// 산술평균 구하기
if(fabs(remain / num) >= 0.5){
if(total < 0){
total = total / num - 1;
}
else if(total > 0){
total = total / num + 1;
}
}
else{
total = total/num;
}
// 중앙값 구하기
middle = result[num/2];
// 최빈값 구하기
for(int i = 0; i < 8001; i++){ // for문으로 mode값 구하기
if(mode <= count[i]){
mode = count[i];
}
}
for(int i = 0; i < 8001; i++){ // for문으로 mode와 count배열의 값 비교해서 같은 값 갯수 찾기
if(mode == count[i]){
boolean++;
}
}
for(int i = 0; i < 8001; i++){ // 최빈값 구하기
if(boolean == 1){
if(mode == count[i]){
result_mode = i- 4000;
break;
}
}
else{
if(mode == count[i]){
boolean = 1;
}
}
}
// 범위 구하기
range = result[num-1] - result[0];
printf("%d\n", total); // 산술평균
printf("%d\n", middle); // 중앙값
printf("%d\n", result_mode); // 최빈값
printf("%d\n", range); // 범위
return 0;
}
Code 필수 요소
1. 산술평균을 위한 반올림 방법
2. 최빈값을 구하고, 여러개일때 두번째 작은수를 출력하는 방법
이것만 생각해내면 절반은 끝났다.
// 배열 입력 및 산술평균을 위한 총합, 최빈값 배열 구하기
배열을 입력하면서 총 합을 나타내는 변수에 더해주고, 최빈값의 배열에 바로바로 추가해준다. 일을 두번 하지 않기 위해서 한번에 처리했다.
여기서 최빈값 배열의 번호가 아주 이상해 보일것이다. 이것은 나중에 최빈값 구하기 파트에서 같이 설명하겠다.
// 반올림을 위한 나머지 계산
C언어에서는 int값을 나누기를 하면 소숫점이 안나오고, %로 계산하면 나머지만 나온다. 그래서 미리 나머지를 구하고, 그 수를 N개로 나누어 소숫점을 얻는 방법을 사용했다.
// 산술평균 구하기
int자료형으로 나눌경우 소숫점이 나오지 않기때문에 remain 변수를 double형으로 상용해주었고, fabs를 통해서 절댓값으로 비교해 주었다. 그래서 반올림이 가능한 경우는 양수와 음수별로 조건처리해주었고, 반올림이 필요없을땐 int자료형으로 나눈 값을 저장했다.
// 중앙값 구하기
배열을 미리 순서대로 정렬해둔 이유다. 순서대로 정렬해둔다면 배열의 중간에 있는 것이 중간값이기 때문에 편하게 찾을수 있다. 또한 미리 정렬을 해두면 이후에 범위를 구할때도 사용한다.
// 최빈값 구하기
이제 제일 어려웠다. 배열을 입력받을때 count[result[i]+4000]++; 라는 내용을 쓴 이유이자, i의 범위가 8001이나 되는 이유는 생각보다 간단하다. 최대 숫자가 4000이고, 음수와 양수를 모두 나타내기 위해서 8001을 사용했다. 여기서 내가 count라는 배열을 어떻게 사용했는지가 내 풀이의 핵심이다.
count배열의 위치는 입력받은 숫자, 값은 입력받은 횟수를 나타낸다.예를 들어보자. count[4000] == 2 일 경우를 보면, 0이라는 숫자를 2번 입력받았다는 것이다. 이러한 방법을 이용해서 mode라는 최다 입력 횟수와 배열의 값이 일치할 경우 최빈값을 가진 숫자가 몇개인지 파악하였다.
최빈값이 하나라면 바로 출력하면 되지만, 2개 이상일 경우 두번째로 작은 숫자를 출력해야 한다. 그래서 boolean을 통해 최빈값이 1개라면 바로 값을 도출하고 for문을 끝냈다. 하지만 boolean이 2이상일 경우 첫번째 최빈값을 발견한 순간 다른 변화 없이 boolean값만을 1로 만들어 다음번에 최빈값을 발견할 경우 값을 도출하고 for문을 끝낼 수 있게 했다.
// 범위 구하기
앞서 말한것 처럼 배열을 초기화 해두었기 때문에 배열의 마지막숫자에서 첫번째 숫자를 빼면 범위가 나온다.
이번 문제에서 나머지는 별로 고민 안하고 해결한거 같은데 최빈값을 도출하는 방법도 어려웠지만, 여러개라면 두번째로 작은 숫자를 출력하라는 조건이 제일 어려웠다. 뇌가 말랑말랑해진거 같다. 난이도는 높지 않지만 해결 아이디어를 짜는게 꽤나 재밌었다.
-꿑-