[BaekJoon/백준] 10989번

계수정렬 = 카운팅정렬 = 도수분포표 정렬을 사용하는 문제다.

 

배운대로 정렬알고리즘을 암만 짜봐도 메모리 초과가 떴다 ㅜ.ㅜ

 

1. 배열 3개 사용 ( 숫자범위 배열 1개 + 요소갯수범위 배열 2개)

-> 메모리 초과

 

2. 1번 방법 + 요소값중에 최댓값과 최솟값을 구해서 숫자범위 배열의 크기를 줄임

-> 메모리 초과

 

허탈한 시간을 보내고 나니, 내가 간과하던 것이 있었다.

 

문제에서 주어진 숫자 범위는 1 ~ 10,000

그리고 문제에서 주어진 요소 갯수 범위는 1 ~ 10,000,000

 

나는 후자에 비하면 매우 작은 전자의 범위만 자꾸 계속해서 줄이려고 한 것ㅋㅋㅋ..

이건 내가 질문글을 열람하면서 알게됐다 ㅠㅜ (웬만하면 질문글 절대안보려는데.... 이번이 두번째..)

 

그리고 메모리 계산에 대해서도 다시한번 생각해보는 계기가 됐다.

 

Byte - > M Byte 니까... 밀리언(100만)을 더하면 되고..

int형인 4byte * 10,000 = 0.04MB

int형인 4byte * 10,000,000 = 40MB

 

 

3. 문제해결. 배열 1개 사용 (숫자범위 배열 1개)

솔직히 내가 카운팅정렬을 애초에 몰랐으면 이 방법을 그냥 바로 썼을 것 같다. 그저 나는 배웠던 카운팅 정렬을 이용하고 싶었기에...

여튼 이 방법은 카운팅 정렬에서 파생되는 방법이라고 볼 수도 있겠다(카운팅정렬보다 장점도 있고 단점도 있음). 이 방법은 이렇게 숫자값의 순서만 출력하는 용도로만 사용할 수 있겠다(안정적이지 않음) 즉, 이런 간단한 유형 한정 적용가능 코드.

 

코드는 매우 간단하다.

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

static int *f;
const int MAX = 10000 + 1;

int main() {
    int nx, temp;
    f = calloc(MAX, sizeof(int));

    scanf("%d", &nx);
    
    for(int i = 0; i < nx; i++) {
        scanf("%d", &temp);
        f[temp]++;
    }

    for(int i = 0; i < MAX; i++) {
        for(int j = 0; j < f[i]; j++) {
            printf("%d\n", i);
        }
    }
    
    free(f);
    return 0;
    
}

 

 

[ 참고하면 좋아용 ]

www.acmicpc.net/board/view/56854

bowbowbow.tistory.com/8