글 읽기 - kth element 사용을 했는데... 시간초과가 나오네요

richard0326 7년 전 0

제가 잘못 사용한 건가요?

중간에 출력 횟수도 출력해보니 최대 O(n)이 나오더라고요.

도와주시면 감사합니다.

#include <cstdio>

int v[5000000];

int quick_sort(int a[], int start, int end, int k);
int partition(int a[], int start, int end);

int main(void)
{
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &v[i]);
	}

	printf("%d\n", quick_sort(v, 0, n-1, k));
	return 0;
}

int quick_sort(int a[], int start, int end, int k)
{
	if (start < end)
	{
		int pivot = partition(a, start, end);
		if (pivot == k - 1)
		{
			return a[pivot];
		}
		else if (pivot > k - 1)
		{
			return quick_sort(a, start, pivot, k);
		}
		else
		{
			return quick_sort(a, pivot + 1, end, k);
		}
	}
}

int partition(int a[], int start, int end)
{
	int pivot = start;
	int i = start;
	int j = end;

	while (i < j)
	{
		while (a[i] < a[pivot] && i < end)
		{
			i++;
		}
		while (a[j] > a[pivot] && j >= start)
		{
			j--;
		}

		if (i < j)
		{
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	int temp = a[pivot];
	a[pivot] = a[j];
	a[j] = temp;
	
	return j;
}

orange4glace 7년 전 1

5 1

1 1 1 1 1

무한루프가 도네요.

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

문제

문제

출처

ICPC

kth element 사용을 했는데... 시간초과가 나오네요

richard0326 7년 전 0

orange4glace 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말