글 읽기 - C++ 언어로 퀵정렬 했는데 시간초과입니다. 도와주세요!

htj889 7년 전 0

점의 개수만큼 입력받고

점의 개수만큼 배열을 동적할당 한 다음에 배열의 맨 앞부터 순서대로 점의 값을 입력받습니다.

그리고 나서 퀵 정렬을 합니다.

#include <iostream>
#include <algorithm>
using namespace std;

class Point {
public:
	int x, y;
	Point() {}
	Point(int _x, int _y) : x(_x), y(_y) {}

	bool operator <= (Point p) {
		if (x < p.x) return true;
		else if (x == p.x && y < p.y) return true;
		else return false;
	}

	bool operator >= (Point p) {
		if (x > p.x) return true;
		else if (x == p.x && y > p.y) return true;
		else return false;
	}

	void print() {
		cout << x << " " << y << endl;
	}
};

class CoordinateSort {
	int size;
	int cursor;
	Point *list;
public:
	CoordinateSort(int _size) : size(_size) { list = new Point[size]; cursor = 0; }
	void append(Point point) {
		list[cursor++] = point;
	}

	void quickSort(int left, int right)
	{
		if (left < right)
		{
			int index = partition(left, right);
			quickSort(left, index - 1);
			quickSort(index + 1, right);
		}
	}

	int partition(int left, int right)
	{
		int first = left;
		Point pivotValue = list[first];

		++left;

		while (left <= right)
		{
			while (list[left] <= pivotValue&&left < right) left++;
			while (list[right] >= pivotValue&&left <= right)right--;

			if (left < right) swap(left, right);
			else break;
		}
		swap(first, right);

		return right;
	}

	void swap(int left, int right)
	{
		Point temp = list[left];
		list[left] = list[right];
		list[right] = temp;
	}

	void print() {
		for (int i = 0; i < size; i++) {
			list[i].print();
		}
	}
};

int main() {
	int testCase; 
	cin >> testCase;
	CoordinateSort coor = CoordinateSort(testCase);
	for (int i = 0; i < testCase; i++) {
		int x, y;
		cin >> x >> y;
		coor.append(Point(x, y));
	}
	coor.quickSort(0, testCase - 1);
	coor.print();
}

kesakiyo 7년 전 1

피봇을 항상 앞에서 잡지 말고 랜덤한 값으로 잡아보세요

정렬된 상태로 들어온다면 O(N^2)으로 작동할 것 같습니다.

htj889 7년 전 0

랜덤한 값으로 잡아보았는데도 시간초과가 일어납니다

코드는 이렇습니다. 메인에서 srand(time(NULL)); 도 해주었구요. ㅠㅠ

int partition(int left, int right)
{
int pivot = rand() % (right - left + 1) + left;
Point pivotValue = list[pivot];

while (left <= right)
{
while (list[left] <= pivotValue&&left < right || left == pivot) left++;
while (list[right] >= pivotValue&&left <= right || right == pivot) right--;
if (left < right) swap(left, right);
else break;
}
swap(pivot, right);

return right;
}

kesakiyo 7년 전 1

이 문제는 입출력 양이 많으므로 빠른 입출력을 사용해야 합니다.

cin, cout보다는 scanf, printf를 권장합니다.

mainpower4309 4년 전 0

시간이 꽤나 오래되어 보실지 모르겠으나....

일단 cin과 cout의 속도를 높이기위해 main에 한줄 선언하였습니다. 또한 줄바꿈 endl은 속도가 느려 '\n'으로 변경하였습니다.

그리고 pivot 잡으실때 배열중에 무작위로 3개 고르고 난뒤 이중에 중간값을 pivot으로 잡으면 좋은 성능이 나옵니다.

괜히 random함수 호출해서 시간 또 잡아먹을 필요가 없죠. 코드 살짝만 바꾸니 잘 실행되고 통과하였습니다.

객체지향으로 너무 잘 푸셔서 저도 코드 보고 배워갑니다....

#include <iostream>

using namespace std;

class Point {
public:
	int x, y;
	Point(): x(0), y(0) {}
	Point(int _x, int _y) : x(_x), y(_y) {}

	bool operator <= (Point p) {
		if (x < p.x) return true;
		else if (x == p.x && y < p.y) return true;
		else return false;
	}

	bool operator >= (Point p) {
		if (x > p.x) return true;
		else if (x == p.x && y > p.y) return true;
		else return false;
	}

	void print() {
		cout << x << " " << y << '\n';
	}
};

class CoordinateSort {
	int size;
	int cursor;
	Point *list;
public:
	CoordinateSort(int _size) : size(_size) { list = new Point[size]; cursor = 0; }
	void append(Point point) {
		list[cursor++] = point;
	}

	void quickSort(int left, int right)
	{
		if (left < right)
		{
			int index = partition(left, right);
			quickSort(left, index - 1);
			quickSort(index + 1, right);
		}
	}

	Point pivot_select(Point a, Point b, Point c) {
		if (a <= b && b <= c)
			return b;
		else if (b <= a && a <= c)
			return a;
		else
			return c;
	}

	int partition(int left, int right)
	{	

		Point pivotValue = pivot_select(list[left], list[static_cast<int>(left+right)/2], list[right]);

		while (left <= right)
		{
			while (list[left] <= pivotValue&&left < right) left++;
			while (list[right] >= pivotValue&&left <= right)right--;

			if (left < right) swap(left, right);
			else break;
		}
		swap(left, right);

		return right;
	}

	void swap(int left, int right)
	{
		Point temp = list[left];
		list[left] = list[right];
		list[right] = temp;
	}

	void print() {
		for (int i = 0; i < size; i++) {
			list[i].print();
		}
	}
};

int main() {

	ios_base::sync_with_stdio(false); cin.tie(NULL);  //for speed up

	int testCase;
	cin >> testCase;
	CoordinateSort coor = CoordinateSort(testCase);
	for (int i = 0; i < testCase; i++) {
		int x, y;
		cin >> x >> y;
		coor.append(Point(x, y));
	}
	coor.quickSort(0, testCase - 1);
	coor.print();

	return 0;
}

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

문제

문제

출처

ICPC

C++ 언어로 퀵정렬 했는데 시간초과입니다. 도와주세요!

htj889 7년 전 0

kesakiyo 7년 전 1

htj889 7년 전 0

kesakiyo 7년 전 1

mainpower4309 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말