백준 10989 : 수 정렬하기 3

또 수 정렬하기다.

 

애초에 문제 잘 보다보면, 카운팅 정렬을 사용하라고 아주 친절하게 나와있다.

카운팅 정렬이란, 

1. 일단 숫자를 쭉 입력받는다.

2. 그 숫자가 몇번 나왔는지 count하는 배열을 만든다.

3. i번째 순서라고 가정할때, count 배열의 i+1번째 방에다 i번의 값을 더해준다.

4. 입력배열을 A, 카운팅 배열을 C, 출력 배열을 B라고 하면

A 배열을 거꾸로 돌리면서 A값의 카운팅 배열 방을 참조한다, 그리고 이 값을 출력배열인 B의 방번호에 넣어준다

설명이 좀 복잡한데, B[C[A[i]]] 가 되는거다. 그리고 이 방의 값은 A[i]를 넣어준다.

그리고 A값의 카운팅 배열 방의 값을 1 빼준다.

5. 이 과정을 반복하면 수가 정렬된다.

 

설명 봐서는 뭔소린지 잘 이해가 안 될 수도 있는데, 그럴거같아서 이 알고리즘을 시각화한 사이트를 가져왔다.

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort

 

그래서,, 이대로 코드를 짰다.

 

#include <stdio.h>

int solve() {
    int test;
    scanf("%d", &test);

    int A[test+1], B[test+1], max = 0;

    //입력
    for(int i=0;i<test;i++)
    scanf("%d", &A[i]);

    //최댓값 찾기
    for(int i=0;i<test;i++) {
        if(A[i] > max)
            max = A[i];
    }

    //숫자별 갯수 카운팅용 배열 초기화
    int C[max+1];
    for(int i=0;i<=max;i++)
        C[i] = 0;

    //숫자별 갯수 카운팅
    for(int i=0;i<test;i++)
        C[A[i]] += 1;

    //카운팅 배열 계산
    for(int i=0;i<=max;i++)
        C[i+1] += C[i];

    //최종 계산
    for(int i=test-1;i>=0;i--) {
        B[C[A[i]]] = A[i];
        C[A[i]]--;
    }

    for(int i=1;i<=test;i++)
        printf("%d\n", B[i]);

}


int main() {
    solve();
    return 0; 
}

 

그래서,, 맞았냐고? 직접 넣어봤으면 알겠지만 메모리 초과가 뜰 것 이다.

알고리즘 순서대로 곧이곧대로 짜면 메모리 오바가 난다 이말이다..

 

#include <stdio.h>
#define size 10001

int C[size] = {0};

int main() {
    int test, temp;
    scanf("%d", &test);

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

    for(int i=0;i<=size;i++) {
        if(C[i] == 0)
            continue;

        for(int j=0;j<C[i];j++)
            printf("%d\n", i);
    }

    return 0; 
}

 

관건은 굳이 배열까지 저장시키면서 할 필요가 없다는거,, 단순 출력이니까