글 읽기 - 반례를 찾지 못하겠습니다..!

ehgns9809 5년 전 0

가수정렬의 원리를 응용한 것인데 std:sort 를 이용했고요

구조체로 입력을 받아서 y좌표 기준으로 오름차순 정렬 후 x좌표 기준으로 다시 정렬해주었습니다

답도 다 맞는것같은데 어디가 문제일까요..?

#include <stdio.h>
#include <algorithm>

using namespace std;



struct pointee {
	int x;
	int y;
};

pointee arr[100001];

bool compare_x(const pointee &a, const pointee &b)
{
	return a.x < b.x;
}

bool compare_y(const pointee &a, const pointee &b)
{
	return a.y < b.y;
}

int main()
{
	
	int N;
	scanf("%d", &N);

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

	sort(arr, arr + N, compare_y);
	sort(arr, arr + N, compare_x);

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

djm03178 5년 전 0

sort는 두 원소가 같을 때 기존의 순서를 유지해준다는 보장이 없습니다. 그래서 y좌표로 먼저 정렬해둔 순서가 x좌표로 정렬할 때 도로 뒤바뀔 수도 있습니다.

같은 원소에 대해 기존의 순서를 유지하는 정렬은 stable_sort입니다.

ehgns9809 5년 전 0

앗 큰 도움이 되었습니다 감사합니다~

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

문제

문제

출처

ICPC

반례를 찾지 못하겠습니다..!

ehgns9809 5년 전 0

djm03178 5년 전 0

ehgns9809 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말