[BOJ 10989] 수정렬하기3

문제출처

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

문제풀이

/**
 * 일반적인 sort로 처음에 풀었는데 메모리초과가 났다.
 * 아이디어적인 문제인데 counting sort를 알게 된 문제.
 * 이 문제의 핵심은 입력받을 수가 10000까지라는 것이다.
 * 정렬문제라고 무조건 sort를 사용하면 안되겠다.
 */

소스코드

#include <iostream>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,input;
    int num[10001]={0,};
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>input;
        num[input]++;
    }
    for(int i=1; i<=10000; i++) {
        while(num[i]--) {
            cout<<i<<"\n";
        }
    }
    return 0;
}