Beakjoon] 수 정렬하기 3 (백준 10989 코테) - 정렬

---

문제주소 : https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

문제 

 

풀이

 - O(nlogn)으로도 풀 수 없는 시간복잡도의 수의 개수를 가지고 있다(10,000,000)
c++의 sort로는 nlogn의 속도의 시간복잡도기에 계수정렬 O(kn)을 통해 풀어야 한다 

 

코드는 아래 숨김

#include <iostream>
#include <vector>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n;
    std::cin >> n;

    //std::vector<int> nums(n, 0);
    std::vector<int> forsort_arr(10001, 0);

    //for (int i = 0; i < n; ++i) {
    //    std::cin >> nums[i];
    //}

    int temp;
    for (int i = 0; i < n; ++i) {
        std::cin >> temp;
        forsort_arr[temp] = forsort_arr[temp] + 1;
    }

    for (int i = 0; i < forsort_arr.size(); ++i) {
        while (forsort_arr[i] > 0) {
            std::cout << i << "\n";
            forsort_arr[i] -= 1;
        }       
    }

    return 0;
}

 

알게 된 것 

 - 기수정렬, 계수정렬에 대해 알게 되었다
 - 기수정렬은 정렬방식이 정말 신박하다.. 큐를 사용해서 간단히 구현도 가능하다.
 - 수의 개수가 많을 땐 시간복잡도뿐만 아니라 메모리도 주의하자.. 저장을 별도의 벡터에 하면 시간복잡도 측면에서는 거의 영향을 받지 않으나 메모리는 두배로 먹게 되어 통과할 수 없다.

---