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

문제

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

---

문제 요약

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하여 출력한다.

 

수의 개수는 1이상 10,000,000이하이다.

수는 10,000보다 작거나 같은 자연수이다.

---

코드

#include <iostream>

#define MAX 10000

using namespace std;

int n;
int input[MAX + 1]; // input[i] : i 등장 횟수

int main() {
	// 입출력 시간 단축
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	// 입력받은 수가 몇번 등장했는지 체크
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		input[num]++;
	}

	// 1 ~ 10000 범위의 모든 수를 체크하여 등장 횟수만큼 출력
	for (int i = 1; i <= MAX; i++) {
		for (int j = 0; j < input[i]; j++) {
			cout << i << "\n";
		}
	}

	return 0;
}

---

코드 설명

계수 정렬(Counting Sort)을 이용하여 문제를 해결한다.

 

계수 정렬은 범위가 작은 수들을 빠르게 정렬할 때 사용하는 방법이다.

 

1. 수를 입력 받으며, 해당 수가 몇 번 입력되었는지를 input배열에 기록한다.

+ 해당 수보다 작은 수가 몇 개 있는지를 통해 몇 번째 위치에 정렬되는지 알 수 있다.

 

2. 1부터 10000까지 반복문을 돌며 각 수의 입력 횟수만큼 출력한다.

---

고찰

위 방법을 사용하면 입출력 시간 초과가 발생하므로 이를 방지하는 코드를 작성해주어야한다.

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

 

처음엔 벡터에 수를 하나씩 넣고, sort함수를 통해 O(nlogn)에 해결하려고 했다.

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

using namespace std;

int n;
vector<int> v;

int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < n; i++) {
		cout << v[i] << "\n";
	}

	return 0;
}

 

하지만 위 방법은 메모리 초과가 발생했다.

 

이 외에도 배열, 우선순위 큐를 통해서도 해봤지만, 역시나 메모리 초과가 발생했다.

 

< 배열을 이용한 시도 >

#include <iostream>
#include <algorithm>

#define MAX_N 10000000

using namespace std;

int n;
int arr[MAX_N];

int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + n);

	for (int i = 0; i < n; i++) {
		cout << arr[i] << "\n";
	}

	return 0;
}

 

< 우선순위 큐를 이용한 시도 >

#include <iostream>
#include <queue>

using namespace std;

int n;
priority_queue<int> pq;

int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		pq.push(-num);
	}

	while (!pq.empty()) {
		int num = -pq.top();
		pq.pop();
		cout << num << "\n";
	}

	return 0;
}

 

좀만 더 생각해보았다면, 똑같이 메모리 초과가 발생하는 문제가 생길거라고 예상했어야 했다.