#11650 좌표 정렬하기

# 문제

# 입력 및 출력

# 풀이

문제가 너무 쉬워서 그냥 풀고 블로그에 올리진 않으려고 했는데 문제를 하나 발견해서 쓰게 됐다

 

1) 처음에 작성한 코드

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning (disable:4996)
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<pair<int,int>> coo;
	for (int i = 0; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		coo.push_back(make_pair(x, y));
	}
	sort(coo.begin(), coo.end());
	while(!coo.empty()){
		printf("%d %d\n", coo.front().first, coo.front().second);
		coo.erase(coo.begin());
	}
}​

이렇게 쓰니까 시간초과가 뜨더라

무슨 문젠가 싶어서 읽어보다가 erase연산이 오래 걸리나 싶어서 찾아보니까

erase연산은 해당 인덱스의 요소를 지우고 모든 요소를 재배치하기 때문에 연산이 오래 걸린다고 한다

http://www.cplusplus.com/reference/vector/vector/erase/

vector::erase - C++ Reference

https://www.acmicpc.net/board/view/26496

글 읽기 - (C++)vector를 쓰면 시간이 오래걸리는건가요?

△ 문제에 대한 답변

 

그래서 내림차순 정렬해서 erase대신 pop_back()을 사용해보았다

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning (disable:4996)
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<pair<int,int>> coo;
	for (int i = 0; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		coo.push_back(make_pair(x, y));
	}
	sort(coo.begin(), coo.end(), greater<>());
	while (!coo.empty()) {
		printf("%d %d\n", coo.back().first, coo.back().second);
		coo.pop_back();
	}
}

재배치가 이루어지지 않아서 시간초과가 뜨지 않았음

 

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning (disable:4996)
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<pair<int,int>> coo;
	for (int i = 0; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		coo.push_back(make_pair(x, y));
	}
	sort(coo.begin(), coo.end());
	for (int i = 0; i < n; i++) {
		printf("%d %d\n", coo.at(i).first, coo.at(i).second);
	}
}

이 문제에선 굳이 삭제 연산이 필요하지 않기 때문에 그냥 인덱스로 접근해서 출력만 해도 됨