방과후
ALGORITHM NOTE약 1분

BOJ 11650 - 좌표 정렬하기

좌표도 줄을 세우면 훨씬 얌전해진다!

#algorithm#boj#silver#sorting
아카이브로 돌아가기

문제 링크

문제

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

입력

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

출력

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

풀이

정렬 기준이 (x 오름차순, y 오름차순)으로 명확하다. 그래서 점들을 배열에 담은 뒤 비교 함수에서 먼저 x를 비교하고, 같을 때만 y를 비교하도록 하면 원하는 순서가 바로 나온다.

코드도 정렬 이후에는 순서대로 출력만 한다. 좌표 자체를 가공하거나 압축할 필요가 없고, 비교 기준을 정확히 구현하는 것이 전부인 문제다.

코드

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
class coordinate {
public:
	int x;
	int y;
	coordinate(int x, int y) : x(x), y(y) { }
};
 
bool compare(coordinate a, coordinate b) {
	if (a.x == b.x)
		return a.y < b.y;
	else
		return a.x < b.x;
}
 
int main() {
 
	int N;
	cin >> N;
 
	int a, b;
	vector<coordinate> coord;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		coord.push_back(coordinate(a, b));
	}
 
	sort(coord.begin(), coord.end(), compare);
 
	int size = coord.size();
	for (int j = 0; j < size; j++)
		cout << coord[j].x << " " << coord[j].y << '\n';
	return 0;
}

복잡도

  • 시간 복잡도: 좌표를 정렬하므로 O(Nlog⁡N)O(N \log N)이다.
  • 공간 복잡도: 좌표 배열을 저장하므로 O(N)O(N)이다.

마무리

좌표 자체를 바꾸는 문제가 아니라 비교 기준을 정확히 세우는 문제다. x를 먼저 보고, 같을 때만 y를 보면 요구한 순서가 그대로 만들어진다.