2751 : 수 정렬하기 2 (C)

 

2751번: 수 정렬하기 2

---

#include<stdio.h>
#define MAX_VALUE 2000002

int n, m;
int a[MAX_VALUE];

int main() {
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++) {
        scanf("%d", &m);
        a[m + 1000001]++;
    }
    for(int i = 0; i < MAX_VALUE; i++) {
        if(a[i] != 0) {
            printf("%d\n", i - 1000001);
        }
    }
    return 0;
}

- 시간 복잡도가 O(NlogN)인 정렬 알고리즘을 사용해서 풀 수 있는 문제이다.

시간 복잡도가 O(NlogN)인 정렬 알고리즘으로는 병합 정렬, 힙 정렬, 계수 정렬 등이 있으며

계수 정렬을 이용해서 문제를 해결했다.

퀵 정렬도 평균 O(NlogN)의 시간 복잡도가 나오지만 최악의 경우 O(N^2)의 시간복잡도가 걸린다.

 

문제에 음수 값도 들어올 수 있어 배열로 구현하여 문제를 해결했다.

Counting Sort는 각 숫자를 하나씩 세면서 정렬하는 알고리즘으로

숫자가 하나 들어왔을 때 그 배열의 인덱스 값을 증가시키고 값을 1로 증가시킨 후

마지막에 배열의 값이 1일 때, 그 인덱스 값을 출력하는 식이다.