pushback

수 정렬하기, 수  정렬하기 2와 다르게 주어진 메모리가 8MB 밖에 없다...

만약 10,000,000개짜리 int형 배열을 선언하면, 40,000,000B = 40,000KB = 40MB 의 메모리가 필요하기 때문에 보나마나 메모리 초과다.

다른 조건을 이용하여 풀어야 한다. 입력 조건을 보면 10,000,000개의 수가 주어지고, 각 수는 10,000보다 크지 않은 자연수라고 한다.

첫 조건은 이미 나가리고... 10,000보다 크지 않은 수라는 점을 이용하여 해결하자.

어떻게 해결하지 생각해보니까 간단하다.

어떤 수가 몇 번 등장했는지만 안다면, 우리는 정렬할 수 있다.

10,001개짜리 배열 arr을 선언하자.

어떤 수를 입력받았을 때, arr[입력받은 수]에 저장된 값을 +1하자.

입력이 끝나면, for문을 통해 i를 1부터 10,000까지 돌면서 arr[i]에 저장된 값만큼 해당 수를 출력해주면 된다.

이와 같이 등장한 수의 개수를 이용한 정렬을 우리는 계수 정렬(Counting Sort)라고 부른다. 이 정렬은 입력 받을 수의 범위를 알아야만 사용 가능하다는 점을 잊지말자 !

#include <iostream>
using namespace std;
int arr[10001] = { 0 , };
int main() {
	ios::ios_base::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
    
	int N, tmp;
	cin >> N;
    
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		arr[tmp]++;
	}
    
	for (int i = 1; i <= 10000; i++) {
		// 등장한 적이 없는 수이기 때문에 패스
		if (arr[i] == 0) continue;
        
		// 등장한 만큼 출력
		while(arr[i]--) {
			cout << i << '\n';
		}
	}

	return 0;
}

수 정렬하기 2 문제를 다시 보니, 이 문제 역시 계수 정렬로 해결가능하다 !

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

bool isExist[2000001];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, tmp;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> tmp;
		isExist[tmp + 1000000] = true;
	}

	for (int i = 0; i < 2000001; ++i) if (isExist[i]) cout << i - 1000000 << '\n';
	return 0;
}

계수 정렬로 해결하니.. 58등으로 3페이지에 위치할 수 있었다.. 굿