#문제
n개의 수가 주어질때 오름차순 정렬하기
제한이 많고, counting sort로 풀어야 되는 것으로 보임 (O(n))

##code
import sys
input = sys.stdin.readlines()

def counting_sort(l):
    max_val = max(l)
    counts = [0 for _ in range(max_val + 1)]
    sorted_arr = [0 for _ in range(len(l))]

    # 횟수 count
    for num in l:
        counts[num] += 1
    # 누적합 배열
    for i in range(1,len(counts)):
        counts[i] += counts [i-1]
    # 정렬
    for num in l[::-1]:
        sorted_arr[counts[num]-1] = num
        counts[num] -= 1

    return sorted_arr


l1 = list(map(lambda x:x.rstrip().replace('\x1a',''),input))
l2 = list(map(int,l1[1:]))

print(counting_sort(l2))

python으로 안되는건지 내가 방법을 모르는건지...


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

void counting_sort(int arr[], int n) {
    int max_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    int* counts = (int*)calloc(max_val + 1, sizeof(int));
    if (counts == NULL) {
        return;
    }

    for (int i = 0; i < n; i++) {
        counts[arr[i]]++;
    }

    int idx = 0;
    for (int i = 0; i <= max_val; i++) {
        while (counts[i] > 0) {
            arr[idx++] = i;
            counts[i]--;
        }
    }

    free(counts);
}

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

    int* l = (int*)malloc(k * sizeof(int));
    if (l == NULL) {
        return 1;
    }

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

    counting_sort(l, k);
    for (int i = 0; i < k; i++) {
        printf("%d\n", l[i]);
    }
    printf("\n");

    free(l);

    return 0;
}

```
c언어로 하면 메모리 초과되는데

이 코드를 짜면서 내가 c언어 동적할당에 대해 모르고 있다는걸 알았다
시험 전까지 c언어 부족한 부분 공부해야...
그리고 알고리즘 짜면서 gpt도움도 받지 않도록 좀 외워가면서 해야겠다 실력이 너무 엉망이다