[백준] 알고리즘 C++ 10989번 - 수 정렬하기3문제

문제

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

10989번: 수 정렬하기 3

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int arr[10001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr[num]++;
	}
	for (int i = 1; i <= 10000; i++) {
		for (int j = 0; j < arr[i]; j++) {
			cout << i << "\n";
		}
	}
}

해설

그냥 아무생각없이 배열 천만까지 만들고 sort해서 제출했는데 당연히 메모리 초과가 뜨게되었다.

그래서 문제에서 제시한게 n의 범위이다.

문제에서의 메모리 8mb를 넘지말라고 되어있다.

10000보다 작은 자연수라고 하였다.

우리는 입력받는 수를 인덱스라 생각하고 배열에다가 카운트를 해준다.

그렇게되면 만번째에 있는 숫자까지 메모리 초과및 시간초과를 피할 수 있다.