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

풀이

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int b[10001]={0};
	for (int i=1; i<=n; i++) {	// 입력 값 count
		int a;
		cin >> a;
		b[a]++;
	}
	for (int i=1; i<=10000; i++) {	// 값 출력
		for (int j=0; j<b[i]; j++)
			cout << i << '\n';
	}
	return 0;
}

개념

ios::sync_with_stdio(false); 는 cin, cout을 scanf, prinf 처럼 빠르게 만들어주는 레퍼런스이다.

 

---

풀이 

 

아주 쉬운 문제처럼 보인다.

하지만 그리 간단하지 않은게, 꽤나 빡센 제한들이 존재한다.

메모리를 최소한으로 사용하기 위해, 주어지는 수가 10,000 이하라는 것에 착안해야한다.

1~10,000의 얼마 차이나지 않는 값들을 비교하여 정렬하기 보다는 1부터 10,000까지 반복하는게 더 빠르다.

 

따라서 값을 받는 즉시, 값에 해당하는 배열에 저장한 뒤 출력시 이를 고려한다.

 

 

---

+a

여러 방식을 시도했었다.

 

①배열을 sort하는 방식

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	int a[10000000];
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}
	sort(a,a+n);
	for (int i=0; i<n; i++) {
		cout << a[i] << '\n';
	}
	return 0;
}

-> 메모리 초과가 발생한다.

 

②vector를 sort하는 방식

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector <int> a(n);
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}
	sort(a.begin(),a.end());
	for (int i=0; i<n; i++) {
		cout << a[i] << '\n';
	}
	return 0;
}

-> 메모리 초과가 발생한다. (stable_sort를 해도 마찬가지)

 

③ios::sync_with_stdio(false)를 사용하지 않았을 때

 

-> 시간초과가 발생한다.

 

---

사실 Radix Sort 방식이 먼저 떠올랐다. 하지만 c++ ctl이 따로 없는 것같고, 구현법이 복잡해 포기했다.

추후에 기수 정렬로도 문제를 해결할 수 있는지 확인해야겠다.