백준 알고리즘 10989번: 수 정렬하기 3 [C++](카운팅 정렬)

문제 출처: www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

1. 코드

#include <iostream>

using namespace std;

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

	int arr[10001] = { 0, };
	int n;
	cin >> n;

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

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

(실행)

2. 풀이

수의 범위가 10000보다 작거나 같은 자연수이기 때문에 카운팅 정렬을 이용하여 문제를 해결해보겠다.

ios::sync_with_stdio(false); //C입출력 방식 사용제한
cin.tie(NULL);	//앞에서 cout으로 출력을 한다면 출력전에 입력부터 진행

위 코드를 넣어서 프로그램의 입출력 속도를 증가시켰다.

int arr[10001] = { 0, };
int n;
cin >> n;

그리고 배열을 10000 크기만큼 선언과 동시에 0으로 초기화시켜준다. 그리고 사용자에게 입력 횟수를 변수 n으로 통해 입력받는다.

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

그리고 사용자에게 n번만큼 값을 input값을 입력받는데 input 위치에 해당하는 배열의 값을 1씩 증가시킨다. 이렇게 되면 해당하는 배열의 값과 인덱스 값을 통해 어떠한 수가 얼마만큼 입력되었는지 확인할 수 있다.

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

그리고 배열을 전체 조회를 하는데 배열 요소의 값이 0인 것은 제외시키고 배열 요소의 값만큼 배열의 인덱스 값을 출력하면 해결된다.