[백준] 2108. 통계학
: solved.ac (자율) - silver 3
https://www.acmicpc.net/problem/2108
2108번: 통계학
첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
www.acmicpc.net
예제 입력 1
5
1
3
8
-2
2
예제 출력 1
2
2
1
10
예제 입력 2
1
4000
예제 출력 2
4000
4000
4000
0
예제 입력 3
5
-1
-2
-3
-1
-2
예제 출력 3
-2
-2
-1
2
예제 입력 4
3
0
0
-1
예제 출력 4
0
0
0
1
정답
#include <stdio.h>
#include <stdlib.h>
int arr[500000];
int count[8001];
int compare(const void* a, const void* b) {
int num1 = *(int*)a;
int num2 = *(int*)b;
if (num1 < num2) return -1;
else if (num1 > num2) return 1;
return 0;
}
int MODE() {
int m = 0;
int cnt = 0;
int num = 0;
for (int i = 0; i < 8001; i++) {
if (count[i] > m) m = count[i];
}
for (int i = 0; i < 8001; i++) {
if (count[i] == m) {
cnt++;
num = i;
}
if (cnt == 2) break;
}
num -= 4000;
return num;
}
int main() {
int n, mid, mode, range;
double avr;
long long int sum = 0;
int min = 4000;
int max = -4000;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
count[arr[i] + 4000]++;
if (arr[i] < min) min = arr[i];
if (arr[i] > max) max = arr[i];
sum += arr[i];
}
qsort(arr, n, sizeof(int), compare);
mid = arr[(n + 1) / 2 - 1];
avr = (double)sum / n;
if (avr > -1 && avr < 0) avr = 0;
range = max - min;
mode = MODE();
printf("%.0f\n", avr);
printf("%d\n", mid);
printf("%d\n", mode);
printf("%d\n", range);
return 0;
}
해설
- 산술평균: 입력되는 모든 수를 더하여 n으로 나눈다.
- 중앙값: 입력을 받은 후 해당 배열을 퀵 정렬하여 (n+1)/2번째 (n이 홀수이므로) 값을 찾는다.
- 범위: 입력된 수 중 최댓값과 최솟값을 찾아 차를 구한다.
- 최빈값 (여러 개라면 그 중 두 번째로 작은 것) :
- 1. 크기가 8000 이상인 배열 count[]를 만든다. (입력되는 정수 크기가 -4000~4000이므로)
- 2. 정수들이 입력될 때마다 그 수에 4000을 더한 값의 count 배열 인덱스를 찾아가 1씩 증가시킨다.
- ex: -4000이 입력되면 count[0]++, 0이 입력되면 count[4000]++, 4000이 입력되면 count[8000]++...
- -> 이 과정이 끝나면 배열 count에는 입력된 모든 수의 입력 횟수가 들어가 있게 될 것이다.
- 3. 배열 count 내의 최댓값(=최빈값의 입력 횟수)을 찾는다.
- 4. 배열을 한 번 더 순회하며 최댓값을 갖는 인덱스(최빈값이 될 수 있는 값)를 찾는다.
- 5. 이때 cnt 변수를 이용하여 횟수를 센다. 최빈값이 나올 때마다 cnt를 1씩 증가시켜 준다.
- 6. cnt가 2가 될 때 (두 번째로 작은 최빈값이 나왔을 때) 반복문을 중지시키고, 해당 인덱스에 4000을 더해 최빈값을 도출한다.
- (최빈값이 하나뿐이라면 cnt는 2가 되지 않을 것이며, 중지 없이 반복문을 돌고 해당 값을 최빈값으로 삼는다.)
1. 헤더와 전역변수 부분이다. 입력되는 정수들을 받을 배열과 그 입력 빈도를 셀 배열을 전역 변수로 선언해 주고,
퀵 정렬 사용을 위해 stdlib.h 헤더파일을 가져왔다. 정렬에 필요한 오름차순 비교 함수도 작성해 주었다.
오름차순 비교 함수와 퀵 정렬 사용 방법에 대해서는 이전 포스팅에 기재했으므로 이번 게시글에서는 상세한 설명을 생략하겠다.
>> 2022.04.02 - [C언어/BAEKJOON] - [백준] 1920. 수 찾기
#include <stdio.h>
#include <stdlib.h>
int arr[500000]; //입력되는 n개의 정수들을 받는 배열
int count[8001]; //정수들이 입력되는 빈도를 세는 배열
//퀵 정렬에서 사용할 오름차순 비교 함수
int compare(const void* a, const void* b) {
int num1 = *(int*)a;
int num2 = *(int*)b;
if (num1 < num2) return -1;
else if (num1 > num2) return 1;
return 0;
}
2. 메인 함수 부분이다. 필요한 변수들을 알맞은 자료형으로 선언 및 초기화해 준다.
- 산술평균은 소수점 한 자리에서 반올림해서 출력해야 한다. 출력하기 전까지는 실수형이어야 하기 때문에 double로 선언했다.
- 산술평균을 구하기 위해서는 입력값의 총합을 담을 변수도 필요하다. 최대 4000의 크기를 갖는 정수가 50만 개까지 들어올 수 있기 때문에 총합이 매우 커질 수 있음을 유의해야 한다. long long int 형으로 선언했다.
- 최솟값과 최댓값은 비교를 위해 일부러 최대, 최소로 (반대쪽) 양극단의 값을 넣어 초기화했다.
입력받을 정수의 개수인 n을 입력받고, n개만큼의 정수를 뒤이어 받는다. 입력과 동시에 몇 가지 조치를 취해 준다.
- 최빈값을 위해 count 배열에 빈도를 기록한다.
- 범위를 위해 최솟값과 최댓값을 찾기 위한 비교를 시행한다.
- 평균을 위해 입력값을 sum 변수에 합산한다.
int main() {
int n, mid, mode, range;
//수의 개수, 중앙값, 최빈값, 범위
double avr; //산술평균
long long int sum = 0; //합계 (평균을 위한)
int min = 4000;
int max = -4000; //최소, 최댓값 (범위를 위한)
scanf("%d", &n); //수의 개수 n 입력
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]); //n개의 줄로 정수 입력
count[arr[i] + 4000]++; //최빈값을 위한 빈도 기록
//-4000은 0, 0은 4000, 4000은 8000 인덱스에 들어감
if (arr[i] < min) min = arr[i]; //최솟값
if (arr[i] > max) max = arr[i]; //최댓값
sum += arr[i]; //평균을 위한 합산
}
3. 입력을 다 받은 후에는 출력이 될 값들을 차례차례 구하고 출력해 준다.
- 중앙값은 퀵 정렬을 통해 자료를 오름차순으로 정렬한 뒤, (n+1)/2 -1 번째 값을 중앙값으로 삼는다.
- 산술평균은 총합 sum을 자료 갯수 n으로 나누어 구한다.
- 범위는 최댓값과 최솟값의 차로 구한다.
- 최빈값은 함수를 통해 구한다. (함수 내용은 후술)
* 이때 산술평균이 -1과 0 사이의 값일 경우 출력이 -0으로 나올 수 있는데,
해당 문제 채점에서는 -0 표기를 인정하지 않으므로 이 경우는 따로 처리하여 0으로 나올 수 있도록 한다.
//퀵 정렬
qsort(arr, n, sizeof(int), compare);
mid = arr[(n + 1) / 2 - 1]; //중앙값 계산
//숫자 개수가 홀수이므로 중앙값은 정렬한 수에서 (n+1)/2번째,
//인덱스가 0부터 시작하므로 (n+1)/2 -1 번째
avr = (double)sum / n; //산술평균 계산
if (avr > -1 && avr < 0) avr = 0; //-0으로 출력되는 경우 방지
range = max - min; //범위 계산 (최댓값 - 최솟값)
mode = MODE();
printf("%.0f\n", avr); //산술평균 출력
printf("%d\n", mid); //중앙값 출력
printf("%d\n", mode); //최빈값 출력
printf("%d\n", range); //범위 출력
return 0;
}
4. 두 번째로 작은 최빈값을 찾는 함수이다.
입력 횟수의 최댓값을 찾기 위해 for문을 한 번, 그 최댓값을 갖는 인덱스를 찾기 위해 for문을 또 한 번 돌도록 했다.
최댓값을 갖는 인덱스가 나올 때마다 cnt를 증가시키고, 해당 인덱스를 별도 변수(num)에 저장한다.
빈도 배열은 -4000부터 4000까지의 입력 횟수를 순서대로 저장해 둔 것이기 때문에 별도의 정렬 과정은 필요하지 않다.
앞에서부터 차례대로 검사해 나가다가 cnt가 2가 되었을 때 (최댓값이 두 번째로 나왔을 때)
이를 두 번째로 작은 최빈값으로 간주, 반복문을 탈출한다.
(만일 cnt가 2가 되지 않고 for문이 끝난다면 최빈값이 두 개 미만(=하나뿐)이라는 것이기 때문에 그 시점에 저장되어 있는 인덱스가 최빈값이 될 것이다.)
이렇게 얻어진 최빈값의 인덱스는 실제 최빈값에서 4000이 더해진 상태이기 때문에, 4000을 도로 빼 준 뒤 리턴하면 된다.
int MODE() { //두 번째로 작은 최빈값을 찾는 함수
int m = 0; //최대 빈도
int cnt = 0; //최대 빈도가 나온 횟수
int num = 0; //최빈값의 인덱스
for (int i = 0; i < 8001; i++) {
if (count[i] > m) m = count[i];
} //빈도 배열을 오름차순으로 돌며 최대 빈도 탐색
for (int i = 0; i < 8001; i++) {
if (count[i] == m) { //최대 빈도를 갖는 값이 나오면
cnt++; //횟수 1 증가
num = i; //해당 값을 최빈값으로 지정
}
if (cnt == 2) break;
//두 번째로 작은 최빈값이 나오면 반복문 탈출
}
num -= 4000;
//빈도 배열에서 0번 인덱스 = -4000의 빈도이므로
//인덱스에 -4000 하여 실제 최빈값 도출
return num;
}