9월 29일(목) - 정렬(11650번 *풀이진행중)

정렬 - 11650번

11650번: 좌표 정렬하기

 

문제점

1. 합병정렬을 사용해야한다는 생각은 든다. 하지만 구조체를 사용하여 비교할 경우가 x,y로 두 가지인 경우의 합병정렬이 문제인 상황

-> void merge 안에서 list[i].x와 list[i].y에 따른 세부적인 조건문을 추가적으로 작성해야할 것 같다

 

 

풀이 - 1차

(합병정렬 추가풀이 작성 필요)

#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
		{
			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", list[i].x, list[i].y);
	}

	return 0;
}