[백준 C++] 10989 수정렬하기3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

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

처음에 메모리제한은 유심히 안봐서 메모리초과가떴다.. 입력값이 최대 10^7개까지가능하고, int형데이터에 전부넣는다면 4bye씩으로 이것만 40mb가 되는셈이다.

보통 시간복잡도를 먼저계산하는데 이 문제는 공간제한에 중점을 두고 풀어야했다.

<처음코드>

#define _CRT_SECURE_NO_WARNINGS //scanf오류 없앰
#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n, *arr;
	scanf("%d", &n);
	arr = new int[n];
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		printf("%d\n", arr[i]);
	}
}

모든 입력값을 배열에 저장하려다가 메모리초과가 떴다.

아래는 입력되는숫자의 최대가 10000인점을 이용하여,
10000개의 배열을 생성후 입력값을 해당 배열의값에 전부 ++ 하였다.
시간제한은 5초라 반복을 10000 + n 돌려도 시간초과는 안뜰것이다.

<수정후코드>

#define _CRT_SECURE_NO_WARNINGS //scanf오류 없앰
#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n, temp;
	int arr[10001] = {0}; //초기화를 해줘야 정상적으로출력
	scanf("%d", &n);
	while (n--) {
		scanf("%d", &temp);
		arr[temp] += 1;
	}
	for (int i = 1; i <= 10000; i++) {
		while (arr[i] > 0) {
			printf("%d\n", i);
			arr[i] -= 1;
		}
	}
}