백준 10989번 - 수 정렬하기 3 (using counting sort)

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

10989번: 수 정렬하기 3

시간도 시간인데 메모리 제한이 8mb이다. 일반적으로 값을 입력받아서 이걸 배열에 저장해서 다른 정렬방법을 사용하면 배열에 저장하고 새로운 배열 만들고 그러는데 메모리가 너무 초과된다.

그러던 중 알아보다가 counting sort, 이번 알분에서 배운 알고리즘을 사용할 수 있는 문제라 사용해보았다.

 

우선 counting sort는 말 그대로 해당 숫자가 몇 개인지 세는 것이다.

예를 들어 내가 5개를 입력한다 가정해보자(5 7 2 2 4)

이러면 배열 index에 맞게 arr[2] = 2; arr[5] = 1; arr[7] = 1; 이런 식으로 저장하는 거지.

그리고 나서 그냥 배열 안의 수만큼 index를 출력해주면 되겠지.

#include <iostream>

#define MAX 10000
using namespace std;

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

	int N;
	cin >> N;

	int arr[MAX+1] = { 0 };
	for (int i = 0; i < N; i++)
	{
		int input;
		cin >> input;
		arr[input]++;
	}

	for (int i = 1; i <= MAX; i++)
	{
		for (int count = 0; count < arr[i]; count++)
		{
			cout << i << '\n';
		}
	}

	return 0;
}

arr[MAX+1] 인 이유는 말 그대로 배열은 0부터 시작이니까. 하지만 내가 원하는건 1부터 10000까지라 +1 해준거지.