백준 10989 수 정렬하기 3

백준 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

[1] velog.io/@aonee/C-%EC%9E%85%EC%B6%9C%EB%A0%A5-%EC%86%8D%EB%8F%84%EC%B0%A8%EC%9D%B4-%ED%95%B4%EA%B2%B0-iossyncwithstdio0