글 읽기 - c++ 퀵소트를 이용한.. 시간 초과..?

husy951 7년 전 0

퀵소트를 이용해서 빠른 정렬 이후 K번째 숫자를 출력하는 소스입니다.

그런데도 시간초과라니요.. ㅠ

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

void quicksort_recursive(vector<long long int>& v, int left, int right) {
	int i = left, j = right;
	int pivot = v[(left + right) / 2];
	// partition
	while (i <= j) {
		while (v[i] < pivot)
			i++;
		while (v[j] > pivot)
			j--;
		if (i <= j) {
			swap(v[i++], v[j--]);
		}
	}
	// recursive call
	if (left < j)
		quicksort_recursive(v, left, j);
	if (i < right)
		quicksort_recursive(v, i, right);
}

void quicksort(vector<long long int>& array) {
	quicksort_recursive(array, 0, array.size() - 1);
}

int main(){

	vector<long long int>park;
	long long int test;
	long long int num;
	long long int jisu;

	cin >> test >> num;

	for (long long int i = 0; i < test; i++) {
		cin >> jisu;
		park.push_back(jisu);
	}

	quicksort(park);

	cout << park[num-1] << "\n";
	
	
	return 0;
}

onjo0127 7년 전 1

scanf보다 상대적으로 느린 cin으로 백만개 정도의 수를 입력받기 때문에 시간초과가 날 수 있습니다.

시작 부분에 ios::sync_with_stdio(false);를 넣어주시면 빨라질거에요 ㅎ

그리고 퀵정렬은 평균 O(NlogN)의 시간복잡도를 가지지만, 최악의 경우에는 O(N^2)이 걸립니다. 이걸 고쳐도 시간초과가 나면 다른 정렬을 찾아보세요...

husy951 7년 전 0

아 ㅁ.... 문제를 잘못 질문했네요 이 문제가 아닌데... ㅎㅎ 이 문제는 맞았습니다.

onjo0127 7년 전 1

K번째 수 문제 맞나요? ㅎㅎ

quick seletion이라는 알고리즘을 찾아보세용

husy951 7년 전 0

네 맞습니다! 알려주신 방법으로 맞았네요 :)

husy951 7년 전 0

그런데 알려주신 ios:: ~~ 이건 어떤 방식이길래 속도가 빨라진겁니까???

onjo0127 7년 전 1

iostream 입출력이 느린 이유가 stdio헤더와 동기화하는 과정 때문에 그런데, 동기화를 꺼주면 빨라지가든요 ㅎㅎ 저코드가 동기화 꺼주는 코드고용

대신 stdio헤더는 같이 못쓰게 되고요

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