[Algorithm] [C++] 백준 10989번 수 정렬하기 3

 

백준 온라인 저지의 10989번 문제입니다.

 

문제 분류는 [정렬]로 분류되어 있습니다.

 

문제 링크 : https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

 

문제 :

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력 :

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력 : 

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 

풀이 : 

- 이 문제는 Counting sort 알고리즘을 적용해서 푸는 문제입니다.

 

- Counting sort, 거창해 보이지만 이 문제를 풀어보면 "아 이거구나 ㅋ"라고 감이 오실겁니다.

 

- 해당 알고리즘에 대해선 추후에 정리해 보도록 하겠습니다만,

 

- 당장 자세한 설명이 알고싶으신 분은 아래 링크에 설명이 잘 되어있습니다.

(이분 설명 잘하시는듯..)

https://bowbowbow.tistory.com/8

Counting Sort : 계수 정렬

핵심은 아래와 같습니다.

1. 먼저 최대 크기+1의 배열을 만들고 0으로 초기화,

2. 값이 들어올 때 마다 해당 배열의 "인덱스"의 값을 +1시켜줌.

 

- 추가적으로, iostream의 cout을 사용하였더니 시간 초과가 발생합니다.

 

- cout과 printf의 실행속도의 차이가 얼마나 큰지 알 수 있는 문제였습니다.

 

 

소스코드 : 

#include<iostream>

using namespace std;
#define MAX_SIZE 10001
int main()
{
	int narr[MAX_SIZE] = { 0, };
	int i, j;
	int num, num1;
	scanf("%d", &num);

	
	for (i = 0; i < num; i++)
	{
		scanf("%d", &num1);
		narr[num1]++;
	}

	for (i = 0; i < 10001; i++)
	{
		if (narr[i])
			for (j = 0; j < narr[i]; j++)
			{
				printf("%d\n", i);
			}
	}

	return 0;

}