백준_11650 (c++)

BOJ_11650

좌표 정렬하기

문제 링크 -> 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개의 줄에 점을 정렬한 결과를 출력한다.

<나의 풀이>

-> 기본 계획

• algorithm 라이브러리에 정의된 sort 함수를 이용한다.
  -> STL 정렬 sort() 함수는 O(nlogn) 의 시간복잡도를 가지므로 상당히 효율적인 정렬 방법이다.

->문제 풀이 코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

#include<string.h>
#include<algorithm>
#include<stdlib.h>


using namespace std;

typedef struct _point {	// 좌표 저장할 구조체 선언
	int y, x;
}_point;
bool cmp(_point a, _point b) {	// sort 함수인자로 사용
	
	if (a.x == b.x) {	// x 좌표가 같은 경우 y좌표 비교
		return a.y < b.y;
	}
	else
		return a.x < b.x;
}
int main() {
	_point point[100000];
	memset(point, 0, sizeof(_point) * 100000);	// 입력받을 배열 초기화
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d",& point[i].x, &point[i].y);
	}
	
	sort(point,point+N,cmp);	// 함수 cmp 를 인자로 사용
	for (int i = 0; i < N; i++) {
		printf("%d %d\n", point[i].x, point[i].y);
	}
}