[C++] 백준 2751번 수 정렬하기 2

오늘은 수업이 있는 날~~

수업 시작하기까지 아직 시간이 남아 도서관에서 기다리면서 문제나 하나 풀어볼까 하다가 이 문제를 골랐다.

 

문제

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

2751번: 수 정렬하기 2

 

사람들이 많이 풀어봤길래 풀어보려고 했는데 문제를 보니까 너무 쉬운 문제였다.

사실... 그냥 지나갈까 하다가 많이 풀어봤으니까 나도 풀어보고 한 문제 더 풀어야겠다는 생각을 가졌다.

 

그런데!!!

 

띠용...반복문도 별로 없는데...

 

//시간 초과된 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	vector<int> a;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int b;
		cin >> b;
		a.push_back(b);
	}
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++) {
		cout << a[i] << endl;
	}

	return 0;
}

이게 시간 초과가 난다고??

 

그래서 찾아보니까(https://www.acmicpc.net/board/view/898)

cout의 경우 endl이 나올 때마다 버퍼를 비우는 등의 부하가 발생해서 endl을 "\n"으로 바꿔도 많이 빨라질 것이라고 한다.

 

위에 대한 내용이 여기서도 잘 설명되어있다.

https://nompangbox.tistory.com/38

 

 

그럼 이제 endl을 \n로 줄바꿈해주면~~

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	vector<int> a;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int b;
		cin >> b;
		a.push_back(b);
	}
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++) {
		cout << a[i] << '\n';
	}

	return 0;
}

 

정답!!

 

 

 

오늘은 쉬운 문제라 그런지 다른 풀이도 다 비슷하였다. 그래서 배열을 이용하여 푸신 분의 코드를 보는데, 배열의 크기가 크므로 전역범위에서 선언한다는 주석을 보고 나도 코드를 작성하면서 고려해야겠다는 생각이 들었다.

#include <iostream>
#include <algorithm>
using namespace std;

int num[1000000];   // 배열의 크기가 크므로 전역범위에서 선언

int main() {
	int N;          // 수의 개수
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	sort(num, num + N);

	for (int i = 0; i < N; i++) {
		cout << num[i] << "\n";
	}

	return 0;
}
출처: https://beginnerdeveloper-lit.tistory.com/106 [초보 개발자의 이야기, 릿허브:티스토리]

 

 

 

 

 

다른 풀이가 딱히 없어서 이번에는 다른 코드를 보다가 발견한 것들에 대해 조사하였다.

 

일단, 첫 번째는 ios::sync_with_stdio(false);

이 코드는 c와 c++의 표준 stream의 동기화를 끊는 역할을 한다. cin과 cout의 속도가 c의 입출력 속도에 비해 느리기 때문에 이 코드를 사용해 속도를 높이는 기능으로 사용한다고 한다.

그래서 시간초과 방지를 위해 아래의 두 줄을 main 시작 부분에 작성해주는 것이라고 한다.

ios::sync_with_stdio(false);
cin.tie(0);

[참고] https://ip99202.github.io/posts/sync_with_stdio(false)-%EC%93%B8-%EB%95%8C-%EC%A3%BC%EC%9D%98%ED%95%A0-%EC%82%AC%ED%95%AD/

https://dingcoding.tistory.com/62

 

두 번째로는 시간 제한 환경에서의 cin, cout보다 빠른 입출력

무턱대고 cin과 cout을 쓰다 보면 속도가 매우 느리기 때문에 오늘처럼 시간초과가 날 수 있다고 한다.

그래서 한번 오늘 코드를 바꿔서 제출해보았다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	vector<int> a;
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int b;
		scanf("%d", &b);
		a.push_back(b);
	}
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++) {
		printf("%d\n", a[i]);
	}

	return 0;
}

결과는 성공!!

 

그런데 느리다고 해서 안 좋은 것이아니고 시간 제한이 있는 코딩테스트 등의 특수한 상황에서의 대처법일 뿐이라고 한다.

cin, cout이 안정성, 확정성 등에서는 더 뛰어나다고 한다.

[참고] https://where-i-am.tistory.com/entry/C-%EA%B8%B0%EB%B3%B8-%EC%9E%85%EC%B6%9C%EB%A0%A5-cin-cout-scanf-printf