[백준 10989] 수 정렬하기 3

🔗문제 풀러가기
단계별로 풀어보기 단계 13의 5번째 문제이다.

문제 분석

시간초과와 메모리초과에 걸리지 않기 위해
계수 정렬 알고리즘을 사용하였다.

코드

#include <iostream>
 using namespace std;

 int arr[10001];

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

	 int n;

	 cin >> n;

	 int a;

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

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

해석

1. 입력받는 n의 수가 최대 10,000밖에 되지 않으므로 10,001길이의 배열에 입력받은 n의 인덱스의 값을 ++한다.
2. 그후 10,001번 만큼 반복문을 돌려 arr의 i번째 인덱스의 값 만큼 i를 출력하면 끝!

cin.tie(NULL);
ios::sync_with_stdio(false);

는 C++의 입출력 속도를 조절하기 위한 명령이다.

출력을 할때 endl을 하면 시간초과가 될 수 있으므로 "\n"으로 줄바꿈 해주어야 한다.