2108)통계학

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

수열이 주어질 때 4가지 대표값들을 찾는 문제다.

4가지 대표값에는 산술평균값, 중앙값, 최빈값, 범위가 있다.

각 대표값들을 구하기 쉽게 주어진 수열을 정렬한다.(퀵 정렬 사용함)

산술평균값은 값을 입력받는 과정에서 합을 구하고 n으로 나눈뒤 반올림한다.

중앙값은 수열의 갯수가 짝수일 때와 홀수일 때를 나누어 생각해야 한다.

수열 갯수가 짝수 개일 때 중앙값을 갖는 항은 없기 때문에

중앙에 인접한 두 항의 평균이 곧 중앙값이 된다.

수열 갯수가 짝수 개일 때 중앙값을 얻기 위한 두 항은 A[N/2], A[N/2-1]이다.

수열 갯수가 홀수 개일 때 중앙값을 얻기 위한 항은 A[(N-1)/2]이다.

최빈값을 구하는 것은 쉽지 않다.

최빈값을 구하기 위한 함수의 초기 상태는 위와 같다.

m은 최빈값이 첫째 항이라 가정한 것이다. Cm은 최빈값이 나타난 횟수다.(1을 한 번 만났으므로 1회를 기록함)

pM은 이전의 최빈값을 저장한다. 이 값 또한 첫째 항을 최빈값으로 취급했다. Cp는 이전 최빈값이 나타난 횟수다.

i=1일 때 Ai와 pM이 같지 않기 때문에 Ai를 pM에 저장하고 Cp를 1로 초기화한다.

Cp가 Cm보다 크지 않기 때문에 그냥 넘어간다.

i=2일 때 Ai와 pM이 같기 때문에 Cp를 하나 증가시킨다.

Cp가 Cm보다 크기 때문에 최빈값을 갱신하기 위해 m에 pM을 넣고 Cm에 Cp를 넣는다.

i=3일 때 Ai와 pM이 같기 때문에 Cp를 하나 증가시킨다.

Cp가 Cm보다 크기 때문에 최빈값 갱신을 위해 m에 pM을 넣고 Cm에 Cp를 넣는다.

이후 동작은 앞에서 언급한 것과 유사하다.

최빈값을 구하는 함수를 만들어 놓으면 최빈값이 같을 때 두 번째 최빈값을 구하는 것은 어렵지 않다.

최초로 같은 갯수의 최빈값을 만날 때(cntOverlap == 0) 최빈값을 갱신하고 cntOverlap을 하나씩 늘린다.

이후에 만나는 같은 갯수의 최빈값들은 cntOverlap이 1보다 크기 때문에 최빈값을 갱신할 수 없다.

범위는 A[n-1]-A[0]이다.

#include<stdio.h>
#include<math.h>
 
void swap(int *A, int *B) {
    int temp;
 
    temp = *A;
    *A = *B;
    *B = temp;
}
 
int partition(int *A, int p, int r) {
    int pivot = (p + r) / 2;
    int i = p - 1;
 
    swap(&A[pivot], &A[r]);
    for (int j = p; j < r; j++) {
        if (A[j] < A[r]) {
            swap(&A[++i], &A[j]);
        }
 
    }
    swap(&A[i + 1], &A[r]);
 
    return i + 1;
}
 
void quickSort(int *A, int p, int r) {
    int q;
 
    if (p < r) {
        q = partition(A, p, r);
        quickSort(A, p, q - 1);
        quickSort(A, q + 1, r);
    }
}
 
int calAverage(int sum, int n) {
    double avg;
    avg = sum / (double)n;
    
    return (int)round(avg);
}
 
int calMedian(int *A, int N) {
    if (N % 2 == 1) return A[(N-1)/2];
    else return (A[N / 2] + A[N / 2 - 1]) / 2;
}
 
int calMode(int *A, int N){
    int mode, preMode;
    int cntMode = 0, cntPreMode = 0;
    int cntOverlap = 0;
 
    mode = A[0]; preMode = A[0];
    cntMode++; cntPreMode++;
 
    for (int i = 1; i < N;i++) {
        
        if (A[i] == preMode) {
            cntPreMode++;
        }
        else {
            preMode = A[i];
            cntPreMode = 1;
        }
 
        if (cntMode < cntPreMode) {
            mode = preMode;
            cntMode = cntPreMode; 
            cntOverlap = 0;
        }
        else if (cntMode == cntPreMode && cntOverlap<1) {
            mode = preMode;
            cntMode = cntPreMode;
            cntOverlap++;
        }
    }
    return mode;
}
 
int calRange(int *A, int N) {
    int range;
 
    range = A[N - 1] - A[0];
    return range;
}
 
int main() {
    int *A;
    int N;
    int sum = 0;
 
    scanf("%d", &N);
    A = (int *)malloc(sizeof(int)*N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        sum += A[i];
    }
    quickSort(A, 0, N - 1);
    
    printf("%d\n", calAverage(sum,N));
    printf("%d\n", calMedian(A,N));
    printf("%d\n", calMode(A,N));
    printf("%d\n", calRange(A,N));
 
    system("pause");
    return 0;
}