[C++] BOJ 11650. 좌표 정렬하기 (feat. std::endl & \n)

출처

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

 

 

 

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

 

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

 

 

풀이

사실 문제를 푸는데 여러 시도를 했다.

 

첫번째 시도로, 유선순위 큐를 활용한 풀이다.

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N = 0;
	cin >> N;
	priority_queue<pair<int, int>, vector<pair<int, int>>,greater<pair<int, int>>> n_arr;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		n_arr.push(make_pair(x, y));
	}
	for (int i = 0; i < N; i++) {
		cout << n_arr.top().first<< " " << n_arr.top().second << endl;
		n_arr.pop();
	}
}

 

우선순위 큐는 내림차순 정렬을 디폴트로 초기화한다. 우리가 구해야 하는 값은 오름차순으로 정렬한 값으로,

오름차순 정렬 시 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>을 활용한다.

 

여기서 시간 초과가 일어났고, PQ의 시간복잡도가 높을 리 없는데...생각하며 일반 sort로도 풀이했다.

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N, x, y;
	cin >> N;
	vector<pair<int, int>> n_arr;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		n_arr.push_back({x, y});
	}
	sort(n_arr.begin(), n_arr.end());
	for (int i = 0; i < N; i++) {
		cout << n_arr[i].first << " " << n_arr[i].second << endl;
	}
	return 0;
}

 

여기서도 시간 초과가 발생했다.

 

여기서부터는 다른 사람의 풀이도 참고해가며 풀어보았다. (맞왜틀;;)

 

 

이 두 풀이에서 잘못된 점은, endl 부분이었다.

cout << endl;에서 endl과 \n의 입출력 시간이 차이가 난다.
endl은 버퍼를 flush하는 과정이 포함되어있어 시간이 조금 더 걸린다.
\n은 버퍼를 비우지 않고, 그대로 남겨두기 때문에 메모리 효율성은 떨어지지만, 시간이 더 빠르다.

 

따라서 해답은, endl이 아닌 \n을 사용하는 것이었다.

#include <bits/stdc++.h>
using namespace std;
#if 0
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N, x, y;
	cin >> N;
	vector<pair<int, int>> n_arr;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		n_arr.push_back({x, y});
	}
	sort(n_arr.begin(), n_arr.end());
	for (int i = 0; i < N; i++) {
		cout << n_arr[i].first << " " << n_arr[i].second << "\n";
	}
	return 0;
}
#endif
#if 0
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N = 0;
	cin >> N;
	priority_queue<pair<int, int>, vector<pair<int, int>>,greater<pair<int, int>>> n_arr;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		n_arr.push(make_pair(x, y));
	}
	for (int i = 0; i < N; i++) {
		cout << n_arr.top().first<< " " << n_arr.top().second << "\n";
		n_arr.pop();
	}
}
#endif