10989 - 수 정렬하기 3

• 난이도: 브론즈 1
• 날짜: 2023년 2월 10일
• 상태: Correct
• 추가 검토 여부: Yes
• 알고리즘 : 메모리 고려

solution

• 본 문제의 최대 테스트 케이스의 수는 천만이다.
• short형 배열을 선언한다고 해도 20MB의 메모리 공간을 소모한다. 문제에서 제한한 메모리 공간은 8MB이니 불가능하다.
• 입력 최대 크기는 10000이므로 0~10000의 정수의 개수를 세는 배열을 선언한다.
• 이 배열의 원소 수만큼 반복하여 출력하면 문제 조건에 부합한다.

code

#include <iostream>
#include <queue>
using namespace std;

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

    int N;
    cin >> N;
    int arr[10001] = {0, };
    int input;
    for(int i = 0; i < N; i++)
    {
        cin >> input;
        arr[input]++;
    }

    for(int i = 1; i <= 10000; i++)
    {
        for(int j = 0; j < arr[i]; j++)
            cout << i << '\n';
    }

    return 0;
}

ref

10989번: 수 정렬하기 3