백준[C언어] 2108: 통계학

✅해결 방법

- quick sort를 사용해서 정렬하고, 최빈값을 구할 땐 counting 배열 만들어서 구함

 

👊Try 1

#include <stdio.h>
#include <stdlib.h>

int cmp(const int *a, const int *b)
{
  if(*a < *b)
    return -1;
  else if(*a > *b)
    return 1;
  else
    return 0;
}

int main()
{
  int i, N;
  int sum=0, max=0;
  float avg;
  int mid, mode=0, range;
  int *a, *f;
  scanf("%d", &N);

  a = calloc(N, sizeof(int));
  for(i=0; i<N; i++)
  {
    scanf("%d", &a[i]);
    sum += a[i];
    max = (max<a[i] ? a[i] : max);
  }
  avg = (float)sum/N;  //평균

  qsort(a, N, sizeof(int), (int(*)(const void*, const void*))cmp);

  mid = a[N/2]; //중앙값

  f = calloc(max+1, sizeof(int));
  for(i=0; i<=max; i++) f[i] = 0;
  for(i=0; i<N; i++) f[a[i]]++;
  for(i=0; i<=max; i++) mode = mode < f[i] ? f[i] : mode;    //최빈값

  range = a[N-1] - a[0];  //범위

  printf("%.0f\n", avg);
  printf("%d\n", mid);
  printf("%d\n", mode);
  printf("%d\n", range);

  free(a);
  free(f);

  return 0;
}

❗런타임오류 (Segfault) : 세그멘테이션 오류

➡️원인: 입력값 범위가 자연수가 아니라 절대값이 4000이하인 정수이므로 f[a[i]]++할 때 f[음수] <--이렇게 잘못된 메모리 접근이 발생해서라고 추정

 

✅어떻게 해결?

- 카운팅 배열 f의 크기를 2배로 늘려서 1~max까지는 음수a[i]값 카운트, max+1~2max까지는 양수a[i]값 카운트 

 

👊Try 2

#include <stdio.h>
#include <stdlib.h>

int cmp(const int*a, const int *b)
{
  if(*a < *b)
    return -1;
  else if(*a > *b)
    return 1;
  else
    return 0;
}

int main()
{
  int i, N;
  int sum=0, max=0;
  double avg;
  int mid, mode=0, range;

  scanf("%d", &N);

  int *a, *f;
  a = calloc(N, sizeof(int));
  for(i=0; i<N; i++)
  {
    scanf("%d", &a[i]);
    sum += a[i];
    max = (max<a[i] ? a[i] : max);
  }
  avg = (double)sum/N;  //평균

  qsort(a, N, sizeof(int), (int(*)(const void*, const void*))cmp);

  mid = a[N/2]; //중앙값

  f = calloc(2*max+1, sizeof(int));
  for(i=0; i<=2*max; i++) f[i] = 0; //초기화
  for(i=0; i<N; i++){
    if(a[i] <= 0)
    {
      f[(-a[i])]++;
    }
    else
    {
      f[2*a[i]]++;
    }
  }
  for(i=0; i<=max; i++) mode = mode < f[i] ? f[i] : mode;    //최빈값

  range = a[N-1] - a[0];  //범위

  printf("%.0f\n", avg);
  printf("%d\n", mid);
  printf("%d\n", mode);
  printf("%d\n", range);

  free(a);
  free(f);

  return 0;
}

❗틀렸습니다

➡️최빈값 여러 개 있을 때는 최빈값 중 두 번째로 작은 값을 출력해야 한다.

 

👊Try 3 : 최빈값 여러 개 있으면 두 번째로 작은 값 출력

/*최빈값 구하는 함수*--counting sort*/
int freqence(int a[], int n, int max)
{
  int i;
  int freq = 0, freq_i; //최빈값 횟수, 최빈값(인덱스)
  int freq_c = 0; //최빈값 개수
  int mode; //반환할 최빈값
  int *f = calloc(2*max+2, sizeof(int));  //카운팅 배열
  

  for(i=0; i<=2*max; i++) f[i] = 0; //초기화

  for(i=0; i<n; i++){   //n번
    if(a[i] <= 0)   //0,음수는 0~max까지에 카운트
    {
      f[(-a[i])]++;
    }
    else    //양수는 n+1~2*max에 카운트
    {
      f[max+1+a[i]]++;
    }
  }

  for(i=0; i<=2*max+1; i++){    //f스캔 하면서
    if(freq <= f[i])
    {
      freq = f[i];  //최빈 횟수
      freq_i = i;   //최빈값
    }
  } 
  
  for(i=0; i<=freq_i; i++)  //최빈값이 몇 개인지 세기
  {
    if(f[i] == freq)    
    {
      freq_c++; //최빈값 개수
    }
  }

  int *m = calloc(freq_c, sizeof(int)); //최빈값 담을 배열
  for(i=0; i<=freq_i; i++)  //f 스캔하면서
  {
    for(int j=0; j<freq_c; j++)
    {
      if(f[i] == freq)  //최빈값 찾으면
      {
        if(i<=max)  //음수 범위에 있는 최빈값의 경우
        {
         m[j] = -i;   //-부호 붙여서 최빈값 저장
        }
        else {
         m[j] = i - max -1;  //양수 범위 최빈값의 경우
        }
      }
    }
  }

  //최빈값 배열 m 탐색
  for(i=0; i<freq_c; i++)
  {
    if(freq_c == 1) //최빈값 1개면
    {
      mode = m[i];
    }
    else{   //최빈값 여러 개면
      mode = m[1];  //두 번째로 작은 값
    }
  }
  return mode;

  free(f);
  free(m);

}

❗️틀렸습니다 

➡️ 원인: 음수/양수 각각 카운트하려고 입력 받은 값 중 최대값 max를 기준으로 2max+2크기의 카운팅 배열을 만들었었는데,

절대값이 max보다 큰 음수의 경우 들어갈 자리가 없게 됨.

 

✅해결

- 입력 수의 범위인 -4000 ~ 4000 을 담을 크기가 8001인 카운팅 배열 1개 선언

- 0~8000까지 반복문을 돌면서 [입력값+4000]자리에 카운트

[0]~[4000] : -4000 ~ 0 (음수, 0) 카운트

[4001] ~ [8000] : 1 ~ 4000 (양수) 카운트

- 최대 등장 횟수 max_f를 구한다

- 다시 0~8000 돌면서 max_f가 두 번 등장하는 순간의 인덱스(==두 번째로 작은 최빈값) 저장

- return 인덱스값 - 4000

 

👊Try 4

/*최빈값 구하는 함수*--counting sort*/
int freqence(int a[], int n)
{
  int i;
  int max_f = 0;  //최대 등장 횟수
  int c_max_f = 0;  //max_f개수 카운트
  int mode;   //최빈값
  int f[8001] = {0};

  for(i=0; i<n; i++)
  {
    f[a[i] + 4000]++;   //카운트
    if(max_f < f[a[i] + 4000])
    {
      max_f = f[a[i] + 4000]; //최대 등장 횟수 구하기
    }
  }

  for(i=0; i<8001; i++)
  {
    if(f[i] == max_f)   //최대등장횟수인 요소 찾으면
    {
      if(c_max_f == 0)
      {
        mode = i;
        c_max_f++;
      }
      else if(c_max_f == 1) //두 번재로 작은 최빈값 만나면
      {
        mode = i;
        break;
      }
    }
  }
  return mode - 4000; //실제 값
}

 

✅전체 코드

#include <stdio.h>
#include <stdlib.h>

int cmp(const int*a, const int *b)
{
  if(*a < *b)
    return -1;
  else if(*a > *b)
    return 1;
  else
    return 0;
}

/*최빈값 구하는 함수*--counting sort*/
int freqence(int a[], int n)
{
  int i;
  int max_f = 0;  //최대 등장 횟수
  int c_max_f = 0;  //max_f개수 카운트
  int mode;   //최빈값
  int f[8001] = {0};

  for(i=0; i<n; i++)
  {
    f[a[i] + 4000]++;   //카운트
    if(max_f < f[a[i] + 4000])
    {
      max_f = f[a[i] + 4000]; //최대 등장 횟수 구하기
    }
  }

  for(i=0; i<8001; i++)
  {
    if(f[i] == max_f)   //최대등장횟수인 요소 찾으면
    {
      if(c_max_f == 0)
      {
        mode = i;
        c_max_f++;
      }
      else if(c_max_f == 1) //두 번재로 작은 최빈값 만나면
      {
        mode = i;
        break;
      }
    }
  }
  return mode - 4000; //실제 값
}

int main()
{
  int i, N;
  int sum=0, max=0;
  double avg;
  int mid, mode, range;

  scanf("%d", &N);

  int *a, *f;
  a = calloc(N, sizeof(int));
  for(i=0; i<N; i++)
  {
    scanf("%d", &a[i]);
    sum += a[i];
    max = (max<a[i] ? a[i] : max);
  }
  avg = (double)sum/N;  //평균

  qsort(a, N, sizeof(int), (int(*)(const void*, const void*))cmp);

  mid = a[N/2]; //중앙값
  mode = freqence(a, N);  //최빈값
  range = a[N-1] - a[0];  //범위

  printf("%.0f\n", avg);
  printf("%d\n", mid);
  printf("%d\n", mode);
  printf("%d\n", range);

  free(a);
  free(f);

  return 0;
}