[백준문제풀이] 10989 수 정렬하기 3

 

풀이 일시 : 2020-08-04

​

 

문제 :

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

​

 

입력:

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

ex)

10

5

2

3

1

4

2

3

5

1

7

​

 

출력:

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

ex)

1

1

2

2

3

3

4

5

5

7

​

 

풀이 :

N이 1000만 이하이기때문에 무조건 O(N)을 요구한다. 대부분의 알고리즘으로는 풀지못하므로 계수정렬로 풀어야 한다.

 

#include <iostream>

using namespace std;
int n,m;
int a[10001]; //모든 수마다 자리가 있어야 된다.

int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> m;
		a[m]++;
	}
	for (int i = 0; i < 10001; i++) {
		while(a[i]!=0){
			cout<<i<<endl;
			a[i]--;
		}
	}
}

 

위와같이 cin, cout을 사용하면 시간초과가 난다.

똑같은 알고리즘이여도 scanf, printf가 더 빠른 것을 알 수 있다. 실제로 scanf, printf는 모든 입출력 방법 중 최상위권의 속도를 낸다. 가장 기초적이고 또 쓸만하다. ㅎㅎ

아래와 같이 작성하면 시간초과가 나지 않는다.. 6번 틀리고 알았다

 

#include <iostream>

using namespace std;
int n,m;
int a[10001]; //모든 수마다 자리가 있어야 된다.

int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &m);
		a[m]++;
	}
	for (int i = 0; i < 10001; i++) {
		while(a[i]!=0){
			printf("%d\n",i);
			a[i]--;
		}
	}
}
​