10월 5일(수) - 정렬(11650번)

정렬 - 11650번

11650번: 좌표 정렬하기

 

문제점

1. 아직까지 알고있던 merge sort는 list[i/j/k].x 만을 활용하는 경우였고, 이번 문제는 list[i/j/k].y 까지 활용해야했다

-> 결국 참조에 있는 코드를 참고하여 풀이했다

-> 아직 merge sort 코드에 대한 확실한 이해가 부족하기 때문에 코드를 추가하는 과정에서 여러번 실패했었다

-> 따라서 merge sort에 대한 추가적인 공부가 필요할 것 같다

 

풀이

(참조 -> https://daydreamx.tistory.com/entry/baekjoon11650)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdlib.h>

typedef struct dot{
	int x;
	int y;
}dot;
dot list[100000];
dot sorted[100000];

void merge(dot* list, int left, int mid, int right)
{
	int i, j, k, l;
	i = left; j = mid + 1; k = left;

	while (i <= mid && j <= right)
	{
		if (list[i].x < list[j].x)
		{
			sorted[k++] = list[i++];
		}
		else if (list[i].x > list[j].x)
		{
			sorted[k++] = list[j++];
		}
		else
		{
			if (list[i].y < list[j].y)
			{
				sorted[k++] = list[i++];
			}
			else if (list[i].y > list[j].y)
			{
				sorted[k++] = list[j++];

			}
		}
	}

	if (i > mid)
	{
		for (l = j; l <= right; l++)
		{
			sorted[k++] = list[l];
		}
	}
	else
	{
		for (l = i; l <= mid; l++)
		{
			sorted[k++] = list[l];
		}
	}
	for (l = left; l <= right; l++)
	{
		list[l] = sorted[l];
	}
}

void merge_sort(dot* list, int left, int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2;
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}

//
int main(void)
{
	int n;
	scanf("%d", &n);

	dot* list = (dot*)malloc(sizeof(dot) * n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &list[i].x);
		scanf("%d", &list[i].y);
	}

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

	return 0;
}