[백준] 11650번 - 좌표 정렬하기

www.acmicpc.net

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

문제

💡

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

시간 제한: 1초

메모리 제한: 256MB

입력

💡

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

출력

💡

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

예제 입력	예제 출력
5 3 4 1 1 1 -1 2 2 3 3	1 -1 1 1 2 2 3 3 3 4

풀이

정렬 함수를 구현하고, 기준을 x가 같은지 우선 확인한 뒤, 같으면 y값을 확인해 오름차순으로 정렬한다.

코드


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

struct Loc {
	int _x;
	int _y;
};

bool comp(Loc a, Loc b) {
	if (a._x != b._x) {
		return a._x < b._x;
	}

	return a._y < b._y;
}


int main() {

	int N;
	cin >> N;
	vector<Loc> arr(N);
	for (int i = 0; i < N; ++i) {
		int x, y;
		cin >> x >> y;
		arr[i]._x = x;
		arr[i]._y = y;
	}

	sort(arr.begin(), arr.end(), comp);

	for (Loc loc : arr) {
		cout << loc._x << " " << loc._y << "\n";
	}
	
	return 0;
}

후기

간단한 정렬 문제이다. x값이 낮은 순으로, x값이 같다면 y값이 낮은 순으로 정렬해야 한다. 점의 좌표이므로 x와 y의 값은 정렬되어도 떨어지지 않아야 한다.

두 점을 저장하기 위해 struct와 pair중 struct를 사용했다. 둘 다 같은 효과이지만, struct가 좀 더 구현이 간단해 사용하였다.

std::sort를 사용했는데, sort는 인트로 소트 방식으로 평균 O(nlogn)속도를 가진다. n은 100,000이므로, 시간은 충분하다.