[C++/백준 10989번] 수 정렬하기 3 (카운팅 정렬)

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

10989번: 수 정렬하기 3

 

해결 방법

  카운팅 정렬을 직접 구현해서 해결했다. 시간 제한이 5초에 메모리 제한이 8MB 라는 것은 많이 크지 않은 수들을 정렬하는 것이기 때문에 int 범위 내에서 해결이 가능하다.

  

  카운팅 정렬에 대한 설명은 아래 블로그를 참고했다. 

카운팅 정렬(Counting Sort, 계수 정렬) 알고리즘

메모리 와 시간 제한에 부합하게 구현한 코드

#include <iostream>

using namespace std;

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


    int N;
    cin >> N;

    int input[10001] = { 0 };

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

    for (int i = 1; i < 10001; i++) {
        for (int j = 0; j < input[i]; j++) {
            cout << i << '\n';
        }
    }

}

 

 

메모리를 신경쓰지 않고 구현한 코드

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int N;

	cin >> N;

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

	int max = -1;
	for (int i = 0 ; i < N ; i++)
	{
		if (max < i)
		{
			max = arr[i];
		}
	}
	
	
	int* cnt = new int[max + 1]{0,};

	
	int i = 0;

	while (i < N)
	{
		cnt[arr[i]]++;
		i++;
	}

	

	i = 1;


	while (i < max)
	{
		cnt[i + 1] = cnt[i] + cnt[i+1];

		i++;
	}



	int* sort = new int[N]{ 0 };

	for (int i = 0; i < N; i++)
	{
		sort[cnt[arr[i]]-1] = arr[i];
		cnt[arr[i]]--;

	}


	for (int i = 0; i < N; i++)
		cout << sort[i] << endl;

	delete[] arr;
	delete[] cnt;
	delete[] sort;
	return 0;
}