10989번 수 정렬하기 3

역시나 풀어보면서, 메모리 초과나 시간 초과가 뜰 것 같았다.

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

메모리 초과 뜬 코드

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
vector<int> v;
 
int main(void)
{
    int N = 0, num = 0;
 
    scanf("%d", &N);
 
    for(int i=0; i<N; i++)
    {
        scanf("%d", &num);
 
        v.push_back(num);
    }
 
    sort(v.begin(), v.end());
 
    int vSize = v.size();
 
    for (int i = 0; i < vSize; i++)
    {
        printf("%d\n", v[i]);
    }
 
    return 0;
}

정답코드

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int num[10000 + 1] = { 0, }; // index와 num[index]가 같은 것을 활용하자.
 
int N = 0;
 
int max_num = 0;
 
void sortNum()
{
    for (int i = 1; i <= max_num; i++) // 10,000까지 갈 필요가 없다.
    {
        if (num[i] == 0) continue; // 0이라는 것은 입력되지 않았다는 것을 의미한다.
 
        for (int j = 0; j < num[i]; j++) // 입력받은 횟수 만큼 출력
        {
            printf("%d\n", i);
        }
    }
}
 
int main(void)
{
    int input_num = 0;
    
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &input_num);
 
        ++num[input_num]; // 입력받은 숫자(input_num)에 대한 배열의 값 1씩 증가
 
        max_num = max(max_num, input_num); 
    }
    
    sortNum(); // 정렬
 
    return 0;
}