글 읽기 - 어떤게 틀린지 모르겠습니다 ㅠ

qktlf789456 3년 전 0

출력 정확하고 stable 한 정렬 merge sort 사용해서 정렬했는데

왜 틀린지 모르겠네요 ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>


/*

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

*/

int size;
int** data;




void merge_sort(int idx, int start, int last)
{



	if (start >= last)
		return;

	int mid = (start + last) / 2;

	merge_sort(idx, start, mid);
	merge_sort(idx, mid + 1, last);



	int** temp = malloc(sizeof(int*) * (last - start + 1));



	int a = start;
	int b = mid + 1;

	int current = 0;
	while (a <= mid && b <= last)
	{
		if (data[a][idx] < data[b][idx])
		{
			temp[current++] = data[a++];
		}
		else
		{
			temp[current++] = data[b++];
		}
	}



	while (a <= mid)
	{
		temp[current++] = data[a++];
	}

	while (b <= last)
	{
		temp[current++] = data[b++];
	}


	for (int i = start; i <= last; i++)
	{
		data[i] = temp[i - start];
	}

	free(temp);
}


int main()
{
	scanf("%d", &size);
	data = malloc(sizeof(int*) * size);

	for (int i = 0; i < size; i++)
	{
		int* temp = malloc(sizeof(int*) * 2);

		scanf("%d", &temp[0]);
		scanf("%d", &temp[1]);

		data[i] = temp;
	}



	merge_sort(0, 0, size - 1);		//정렬할 인덱스순서, start, last
	merge_sort(1, 0, size - 1);



	//output
	for (int i = 0; i < size; i++)
	{
		printf("%d %d\n", data[i][0], data[i][1]);
	}
	return 0;
}

kyo20111 3년 전 1

2번째 원소를 먼저 고려합니다.

input:
2
1 100
2 1

ans:
1 100
2 1

kyo20111 3년 전 1

47번째 if문을 이렇게 교환하면 아마 idx 없이 함수 호출 한번이면 될 것 같습니다.

if(data[a][0] < data[b][0] || (data[a][0] == data[b][0] && data[a][1] < data[b][1]))

luniro 3년 전 1

47번 째 줄 if (data[a][idx] < data[b][idx]) 여기에 등호가 없어도 stable한가요?

qktlf789456 3년 전 0

너무 감사합니다댓글 .. merge sort에서 stable 을 간과하고있었기도 했고 ㅠ 함수를 한번으로 해결할수도있었네요..! 참 코딩은 멀고 험한 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤게 틀린지 모르겠습니다 ㅠ

qktlf789456 3년 전 0

kyo20111 3년 전 1

kyo20111 3년 전 1

luniro 3년 전 1

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말