알고리즘/백준(BOJ)
백준 10989 수 정렬하기 3
오뚜깅
2021. 1. 17. 03:59
반응형
백준 10989 수 정렬하기 3 문제는 내게 시행착오를 많이 겪게 했다.
나는 Visual Studio로 먼저 문제를 풀어보고 답이 나오면 제출하곤 하는데, 보통 이렇게 해도 메모리 초과, 출력 초과 등 여러 문제로 틀리곤 한다.
먼저 이 문제는 문제 설명란에 분명 "수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다." 라고 써있었다.
카운팅 정렬 알고리즘을 공부하고 풀어보면, 이 문제는 메모리 초과로 틀리게 된다.
8MB 로 메모리 제한이 있기 때문이다.
C++ 입출력 속도차이를 아래와 같은 방법으로 해결해야한다.
ios::sync_with_stdio(false);
=> C 표준 stream과 C++ 표준 stream의 동기화를 끊는 것을 의미한다.
cin.tie(NULL);
cout.tie(NULL);을
=> cin을 cout으로부터 untie를 한다는 의미인데, stream을 tie 하면 다른 stream 에서 입출력 요청이 오기전에 stream을 flush 시킨다.
이 것을 사용하는 이유는 cin, cout이 scanf, printf 보다 많이 느리기 때문에 속도를 가속시키기 위하여 사용하는 것이다.
두 번째로 신경 썼던 부분은 int count[10001] = {0}; 으로 초기화 시켜 사용한 것이다.
초기화 하지 않고 사용하면 배열이 쓰레기 값으로 생성되기 때문에 어떤 경우에는 출력 초과로 이어질 수 있다.
이런 점들을 신경쓰고 나면 알고리즘 자체는 큰 어려움이 없다.
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
int count[10001] = {0};
for (int i = 0; i < N; i++) {
int temp;
cin >> temp;
count[temp]++;
}
for (int i = 1; i <= 10000; i++) {
for (int c = 0; c < count[i]; c++) {
cout << i << "\n";
}
}
return 0;
}
Reference
반응형