백준[C언어] 10989: 수 정렬하기 3

✅문제

- N개의 수를 오름차순으로 정렬하는 간단한 문제이다.

 

❗주의해야 하는 것은 메모리 제한과 수의 범위가 10,000으로 작다는 것이다.

➡️quick sort로 풀면 메모리 초과가 뜬다.

따라서, counting sort(도수 정렬)을 사용하는 것이 적합하다. 

 

🔺counting sort 특징

장점: 단일 for문으로만 구성되어 있어 매우 빠르고 효율적이다.

단점: 최대값과 최소값을 알고 있는 경우에 한해 효율적이다. (도수분포표 위한 배열이 따로 필요)

-> 수의 범위가 작은 경우에 적합하다.

 

✅Counting sort (도수 정렬)

step 1. 도수분포표 만들기

- 데이터가 있는 배열 a를 스캔하며 배열 a의 요소값을 인덱스로 하는 도수분포표 배열 f에 카운트

step 2. 누적도수분포표 만들기

- 배열 f의 현재 요소와 바로 앞 요소값을 더해서 현재 인덱스에 저장

step3. 목적 배열 만들기

*맨 끝요소 a[n-1] 부터 스캔해야 함. 처음부터 스캔하면 a에서 중복값 발견 시 먼저 위치했던 값이 b에서는 더 뒤에 우치하게 되므로 순서가 뒤바뀌게 됨.(즉, 안정적이지 않은 알고리즘) 

step 4. 배열 b를 배열 a로 복사

 

👊Try 1

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


void fsort(int a[], int n, int max) 
{
  int i;
  int *f = calloc(max, sizeof(int));
  int *b = calloc(n, sizeof(int));

  for(i=0; i<=max; i++) f[i] = 0; //배열 f 0으로 모두 초기화
  for(i=0; i<n; i++) f[a[i]]++; //step 1: a스캔하며 f에 카운트
  for(i=0; i<=max; i++) f[i] = f[i-1] + f[i]; //step 2: 누적하기
  for(i=n-1; i>=0; i--) b[--f[a[i]]] = a[i];  //step 3: 목적배열
  for(i=0; i<n; i++) a[i] = b[i]; //step 4: 배열 복사

  free(b);
  free(f);
}

int main()
{
  int i;
  int N;
  int max = 0;
  scanf("%d", &N);
  int *a = calloc(N, sizeof(int));

  for(i = 0; i<N; i++)
  {
    scanf("%d", &a[i]);
    max = max<a[i] ? a[i] : max;
  }


  fsort(a, N, max);

  for(i=0; i<N; i++)
  {
    printf("%d\n", a[i]);
  }

}

❗메모리 초과 

➡️문제에서 제한한 메모리는 8 MB인데 n개의 데이터를 받아서 배열 a에 넣을 때 최대 4 * 10,000,000 byte (40 MB) 사용되니까 배열 a 만들 때부터 이미 범위를 넘어감.

 

✅어떻게 해결?

 크기가 10,001인 배열 (a)을 하나만 만들어서 입력된 값에 해당하는 인덱스(a[])에 count

 

👊Try 2

#include <stdio.h>


int main()
{
  int i;
  int N;
  scanf("%d", &N);  //N개의 수
  int value;
  int max = 0;
  int a[10001] = {0};

  for(i = 0; i<N; i++)  //N번 입력받음
  {
    scanf("%d", &value);
    a[value]++;   //받은 값에 해당하는 인덱스에 count
    max = (max < value ? value : max);  //최대값 구하기
  }

  for(i=1; i<=max; i++)   //1~최대값까지의 인덱스 범위에서 a 스캔
  {
    if(a[i] > 0)   //개수가 1개 이상인 것만 생각
    {
      for(int j=0; j<a[i]; j++)   //그 개수만큼 출력
      {
        printf("%d\n", i);
      }
    }
  }

}

⭕맞았습니다!