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

블로그에 올리는 모든 문제 풀이는 깃허브에 올려져 있습니다.

---

문제 설명

• N(1 <=N <=10,000,000) 개의 정수가 주어진다.
  둘째 줄은 N개의 10,000보다 작거나 같은 자연수가 주어진다.
  이를 오름차순으로 정렬하는 프로그램을 작성하시오.

---

풀이 전략

• 배열의 인덱스를 특정한 데이터의 값으로 보며, 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정했다. (=계수 정렬)
• cin, cout은 scanf, printf보다 속도가 느려서 시간 초과가 나므로, sync_with_stdio를 사용하여 속도를 향상한다.
• sync_with_stdio
  - C 표준 stream과 C++ 표준 stream의 동기화를 끊는다.
  - 동기화를 끊으면 사용하는 버퍼의 수가 줄어들어 속도가 향상됨
• cin.tie(NULL) / cout.tie(NULL)
  - cin과 cout을 untie 한다.
  - 사용 시 C 표준 입출력과 혼용하지 말아야 한다.

소스 코드

#include <iostream>

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

	int n;
	cin >> n;

	int arr[ 10001 ] = { 0 };

	for ( int i = 0; i < n; i++ )
	{
		int x;
		cin >> x;

		arr[ x ] += 1;
	}

	for ( int i = 0; i < 10001; i++ )
	{
		if ( arr[ i ] == 0 )
			continue;

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

---

링크

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

10989번: 수 정렬하기 3