[정렬] BOJ 10989번 수정렬하기 3 - 오답노트

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

- 문제 파악

최대 10000000개의 정수(정수의 범위는 1부터 10000)가 입력 이를 오름차순으로 정렬하여 출력하라

 

- 나의 접근

Merge Sort 또는 STL sort 함수 둘 중 하나라도 사용할려면 10000000개의 배열이 필요한데 이러면 메모리 초과다.

그리고 시간 복잡도도 엄청나게 올라갈 것..

 

- 정답

정답은 의외로 간단하다..

정수의 범위는 1부터 10000이므로 10000개 배열을 만들고 정수가 들어오면 그 정수의 개수를 배열에 저장하면 된다..

 

알고리즘을 공부하려고 문제를 풀었으나, 알고리즘을 쓰기 위해서 문제해결 능력을 개밥줘버렸다..

 

<추가>

아래 알고리즘은 Counting Sort로 주어지는 n개의 정수를 보는 것보다 정수의 범위가 상대적으로 좁으므로 정수의 개수를 세는 것이 더 효율적이다

 

#include "bits/stdc++.h"

using namespace std;

int arr[10001];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n, input;
    cin>>n;
    for(int i = 0 ; i < n; i++)
    {       
        cin>>input;
        arr[input]++;
    }
        
    for(int i = 0 ; i < 10001; i++)
    {
        while(arr[i]--)
        {
            cout<<i<<"\n";
        }
            
    }
        
    
    
}