문제

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

---

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; 
	cin >> n; 

	vector<int> arr; 
	for(int i = 0; i < n; i++){
		int x; 
		cin >> x; 
		arr.push_back(x); 
	}

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

	for(auto e: arr){
		cout << e << "\n"; 
	}
	
    return 0;
}

위와 같이 일반적인 방법으로 풀면 메모리 초과가 발생한다. 문제에 주어진 조건을 보면, 최대 입력 크기는 1000만인데 메모리 제한은 8MB이다.

int 하나당 4B이므로 입력값을 모두 배열에 저장하려면, 최대 4B * 10^7 = 40 MB의 메모리가 필요하다.

따라서 입력값을 배열에 저장하여 sort 하는 방식으로는 이 문제를 해결할 수 없다.

계수 정렬 (Counting Sort)

문제에 주어진 예제 입력을 다시 보자.

10
5
2
3
1
4
2
3
5
1
7

i	count[i]
1	2
2	2
3	2
4	1
5	2
6	0
7	1

이렇게 i (1이상 10000이하의 자연수) 라는 숫자가 입력된 횟수를 카운팅 한 다음에, i를 count[i]만큼 출력하면 답을 구할 수 있다. i가 기본적으로 정렬되어 있는 상태이기 때문에 그 숫자가 입력된 횟수만큼만 출력해주면 된다. 이 방식으로 풀면 입력값을 굳이 배열에 저장할 필요가 없다.

이를 계수 정렬이라고 부르는데 다음과 같은 제약조건이 있다.

1. 데이터(값)은 0 또는 양의 정수여야 한다. (값 자체를 인덱스로 사용하므로)
2. 값의 범위가 너무 크지 않아야 한다. (메모리 크기를 넘어서는 안 된다.)

이 문제도 최대 입력값이 1만이므로 count 배열을 위해서는 4B * 10000 = 40KB 정도의 메모리 공간이 필요하다. 따라서 문제 조건에 부합하여 메모리 초과가 발생하지 않는다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define MAX 10001
using namespace std;

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; 
	cin >> n;

	int count[MAX] {0};

	for(int i = 0; i < n; i++){
		int x; 
		cin >> x; 

		// x가 입력된 횟수 카운팅 
		count[x] += 1; 
	}

	// i를 j번 출력 
	for(int i = 1; i < MAX; i++){
		for(int j = 0; j < count[i]; j++){
			cout << i << "\n"; 
		}
	}

    return 0;
}