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 하는 방식으로는 이 문제를 해결할 수 없다.
문제에 주어진 예제 입력을 다시 보자.
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가 기본적으로 정렬되어 있는 상태이기 때문에 그 숫자가 입력된 횟수만큼만 출력해주면 된다. 이 방식으로 풀면 입력값을 굳이 배열에 저장할 필요가 없다.
이를 계수 정렬이라고 부르는데 다음과 같은 제약조건이 있다.
- 데이터(값)은 0 또는 양의 정수여야 한다. (값 자체를 인덱스로 사용하므로)
- 값의 범위가 너무 크지 않아야 한다. (메모리 크기를 넘어서는 안 된다.)
이 문제도 최대 입력값이 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;
}