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

문제

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

10989번: 수 정렬하기 3

 

풀이

굉장히 쉬운 정렬 문제인 줄 알고 그냥 들이댔다가 큰코다쳤다. 

메모리 초과가 뜬 걸 보고 문제를 다시 천천히 읽었다. N이 10,000,000까지 가능하다. 

이를 전부 입력받고 sort()하면 메모리가 남아나질않음을 인지했어야 했다.

 

다시 문제를 처음으로 돌아가 result배열에 한 칸씩 카운트를 늘려주는 방식으로 풀었다. (입력 숫자는 10000 이하이므로)

좋은 문제 같다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int result[10001];
int N;
int main() {
//단순하게 sort()로 풀면 메모리초과 (공간복잡도)
//입력값을 전부 저장하면 메모리 초과 (10,000,000)
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;

		result[a]++;
	}
	//탐색
	for (int j = 0; j < 10001; j++) {
		for (int k = 0; k<result[j];k++){
			if (result[j] == 0) break;
			else{
				cout << j << '\n';
			}


		}

	}

	return 0;
}