글 읽기 - 시간 초과 질문 드립니다

skatjdehddms 2년 전 0

시간을 줄이려면 병합정렬을 써야한다고 해서 급하게 배워서 써봤는데 그래도 시간초과가 납니다 제가 병합정렬을 잘 쓴건지도 잘 모르겠습니다 틀리게 사용한 부분이나 잘못된 부분 있으면 따끔하게 한마디 해주십쇼

#include<iostream>
using namespace std;

class point
{
private:
	int x, y;
public:
	void copy(class point& p)
	{
		x = p.x;
		y = p.y;
	}
	point(int a, int b)
		:x(a), y(b)
	{

	}
	point()
	{

	}
	void init(int a, int b)
	{
		x = a;
		y = b;
	}
	int getx()
	{
		return x;
	}
	int gety()
	{
		return y;
	}
};


void sort(point arr[], int left, int right, point t[])
{
	int L = left;
	int mid = (left + right) / 2;
	int R = mid + 1;
	int k = left;
	while (L <= mid && R <= right)
	{
		//t[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++];
		if (arr[L].getx() < arr[R].getx())
			t[k++].copy(arr[L++]);
		else if (arr[L].getx() > arr[R].getx())
			t[k++].copy(arr[R++]);
		else
		{
			while (L <= mid && R <= right)
			{
				//t[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++];
				if (arr[L].gety() < arr[R].gety())
					t[k++].copy(arr[L++]);
				else if (arr[L].gety() > arr[R].gety())
					t[k++].copy(arr[R++]);

			}
		}

	}
	if (L > mid)
	{
		for (int i = R; i <= right; i++)
			t[k++] = arr[i];
	}
	else
	{
		for (int i = L; i <= mid; i++)
			t[k++] = arr[i];
	}
	for (int i = left; i <= right; i++)
	{
		arr[i].copy(t[i]);
	}
}
void saperate(point arr[], int left, int right, point t[])
{
	if (left == right)
	{
		return;
	}
	int mid;
	mid = (left + right) / 2;
	saperate(arr, left, mid, t);
	saperate(arr, mid + 1, right, t);
	sort(arr, left, right, t);
}

int main()
{
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(0);
	int a;
	cin >> a;
		point* t = new point[a];
	point* p = new point[a];
	for (int i = 0; i < a; i++)
	{
		int x, y;
		cin >> x >> y;
		p[i].init(x, y);
	}
	saperate(p, 0, a - 1, t);
	for (int i = 0; i < a; i++)
	{
		cout << p[i].getx() << " " << p[i].gety() << "\n";
	}
	return 0;
}

zenith82114 2년 전 1

sort 함수에서 양쪽을 합치다가 두 점의 x좌표가 같으면 52줄의 else로 들어가는데

그 뒤부터는 계속 y좌표로 정렬을 하게 되는 게 첫 번째 문제고,

여기서 두 점의 y좌표가 같으면 무한 루프에 빠지는 게 두 번째 문제입니다.

skatjdehddms 2년 전 0

복사 붙여넣기 하다가 while까지 넣어버렸네요 너무 감사합니다

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

문제

문제

출처

ICPC

시간 초과 질문 드립니다

skatjdehddms 2년 전 0

zenith82114 2년 전 1

skatjdehddms 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말