알고리즘 문제풀이/백준문제풀이
[백준문제풀이] 10989 수 정렬하기 3
로디네로
2020. 12. 29. 01:19
반응형
풀이 일시 : 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]--;
}
}
}
반응형