백준 11651 좌표정렬하기2 C/C++

좌표 정렬하기 2 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

49275

32002

27252

67.369%

문제

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

입력

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

출력

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

예제 입력 1 복사

5
0 4
1 2
1 -1
2 2
3 3

예제 출력 1 복사

1 -1
1 2
2 2
3 3
0 4

#include <iostream>
#include <cstring>

using namespace std;


typedef struct
{
	int x;
	int y;
}point;


void MergeTwoArea(point*arr, int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	point* sortArr = (point*)malloc(sizeof(point) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx].y < arr[rIdx].y)
			sortArr[sIdx] = arr[fIdx++];
		else if(arr[fIdx].y > arr[rIdx].y)
			sortArr[sIdx] = arr[rIdx++];
		else
		{
			if (arr[fIdx].x< arr[rIdx].x)
				sortArr[sIdx] = arr[fIdx++];
			else
				sortArr[sIdx] = arr[rIdx++];
		}
		sIdx++;
	}

	if (fIdx > mid)
	{
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

void MergeSort(point* arr, int left, int right)
{
	int mid;

	if (left < right)
	{
		// 중간 지점을 계산한다.
		mid = (left + right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);

		// 정렬된 두 배열을 병합한다.
		MergeTwoArea(arr, left, mid, right);
	}
}



point arr[100001];
int main(void)
{
	int n;
	
	cin >> n;


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

	MergeSort(arr, 0, n - 1);


	for (int i = 0; i < n; i++)
	{
		printf("%d %d \n", arr[i].x, arr[i].y);
	}
	return 0;
}

 

좌표 정렬하기1이랑 똑같은 문제인데, y위주로 정렬하면 된다.

 

병합정렬로 y로 순서로 정렬

다 정렬된 이후에 값이 남을 경우 x가 작은 순으로 삽입을 하면 정렬이 완료된다.