백준 Back_Joon(11650 좌표정렬)- C++

---

개요

 

이번에는 좌표 정렬 문제를 풀어보았습니다.

 

---

문제

 

 

---

풀이

 

이문제에서 중요한 것은 시간 초과를 어떻게 잘 해결하느냐 인데

C++ algorithm의 해더파일을 선언하여

sort함수를 사용하였습니다.

이 sort함수는 퀵정렬을 사용하여 O(nlogn)이 적용되었습니다.

sort(start, end)를 사용하여 [start, end]의 범위에 있는 인자를 오름차순으로 정렬해줍니다

그리고 sort(start,end,compare)와 같이 3번째 인자에 사용자가 정의한

함수를 기준으로 정렬을 할 수 있습니다.

 

처음에 구조체를 이용해서 풀게 되었는데 

Point P[100001]때문에 시간 초과가 떴던 것 같습니다.

그래서 Vector를 이용하여 풀어 보았습니다.

 

---

struct를 배열에 넣어 풀었을 때

 

// 좌표정렬 문제

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

struct Point
{
	int x, y;
};
bool compare(Point p1, Point p2) {
	if (p1.x == p2.x) {
		return p1.y < p2.y;
	}
	else {
		return p1.x < p2.x;
	}
}
int main() {

	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	Point P[100001] = { 0, };
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> P[i].x >> P[i].y;
	}
	sort(P, P + N, compare);
	
	for (int i = 0; i < N; i++) {
		cout << P[i].x << " " << P[i].y;
		printf("\n");
	}

	return 0;
}

 

---

vector를 이용하여 풀었을 때

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;

struct Point {
	int x;
	int y;
};

bool cmp(Point p1,Point p2) {
	if (p1.x < p2.x) return true;
	else if (p1.x == p2.x) {
		return p1.y < p2.y;
	}
	else return false;
}

int main() {

	int n;
	cin >> n;

	vector <Point> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i].x >> p[i].y;
	}

	sort(p.begin(), p.end(), cmp);

	for (int i = 0; i < p.size(); i++) {
		cout << p[i].x << " " << p[i].y;
		printf("\n");
	}
}

 

 

이렇게 하게 될 경우에는 시간 초과가 발생하지 않게 됩니다. 그리고 cout <<endl; 은 시간을 많이 잡아먹기 때문에 

printf("\n")로 바꾸어 주었습니다.

 

---

결과

 

 

---