글 읽기 - vector와 sort없이 푸는 방법이 있을까요?

ahrrudals 1년 전 0

퀵 정렬을 이용하여 풀어보려 했는데 어떤게 문제인지 잘 모르겠습니다....ㅠㅠ

#include <iostream>

using namespace std;
int x_arr[100000];
int y_arr[100000];
void swap(int y_arr[], int x_arr[], int i, int j) {
	int imsi1,imsi2;
	imsi1 = y_arr[i];
	y_arr[i] = y_arr[j];
	y_arr[j] = imsi1;
	imsi2 = x_arr[i];
	x_arr[i] = x_arr[j];
	x_arr[j] = imsi2;
}
int parti(int y_arr[], int x_arr[],int left, int right) {
	int i = left - 1;
	int pivot = y_arr[right];
	int pivot_x = x_arr[right];

	for (int j = left;j < right;++j) {
		if (y_arr[j] < pivot) {
			++i;
			swap(y_arr, x_arr, i, j);
		}
		else if (y_arr[j] = pivot) {
			if (x_arr[j] < pivot_x) {
				++i;
				swap(y_arr, x_arr, i, j);
			}
		}	
	}

	swap(y_arr,x_arr, i + 1, right);

	return i + 1;
}

void qsort_re(int y_arr[], int x_arr[], int left, int right) {
	if (left >= right) return;

	int pivotpo = parti(y_arr, x_arr, left, right);

	qsort_re(y_arr, x_arr, left, pivotpo - 1);
	qsort_re(y_arr, x_arr, pivotpo + 1, right);
}

void q_sort(int y_arr[],int x_arr[],int n) {
	qsort_re(y_arr, x_arr, 0, n - 1);
}


int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	for (int j = 0; j < n;j++) {
		cin >> x_arr[j];
		cin>>y_arr[j];
	}
	q_sort(y_arr, x_arr, n);
	for (int k = 0;k < n;k++) {
		cout << x_arr[k] << " " << y_arr[k] << "\n";
	}

}

pill27211 1년 전 0

애초에 퀵 정렬은 O(N^2)의 복잡도를 갖습니다. 즉, N이 최대 10만개까지 들어올 수 있는 문제에선 최악의 경우 100억회의 연산까지 수행해야 할텐데 과연 제한 시간 1초내에 수행할 수 있을까요?

ahrrudals 1년 전 0

제한 시간과 별개로 결과만 올바르게 얻을수 있도록 수정할수 있을까요? 다른 방법으로 맞추긴 했는데 저 방법으로 결과가 나올수 있을지가 궁금해서,,,

djm03178 1년 전 0

자세히 보지는 않았지만 25번째 줄에 ==가 아닌 =가 들어있네요.

ahrrudals 1년 전 0

^^;;;,,, 해결됐습니다 감사합니다... ㅠㅠㅠ

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

문제

문제

출처

ICPC

vector와 sort없이 푸는 방법이 있을까요?

ahrrudals 1년 전 0

pill27211 1년 전 0

ahrrudals 1년 전 0

djm03178 1년 전 0

ahrrudals 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말