글 읽기 - 시간초과 문제

hwider 6년 전 0

시간 초과가 나는데 어느 부분인지 모르겠습니다ㅠㅠ

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

void quickSort(int A[], int left, int right);
int partition(int A[], int left, int right);

int main()
{
	int N, K;
	cin >> N >> K;

	//int arr[5000001];
	int *arr = new int[5000001];

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	quickSort(arr, 0, N - 1);
	cout << arr[K - 1];
}



void quickSort(int A[], int left, int right)
{
	if (left < right)
	{
		int q = partition(A, left, right);
		quickSort(A, left, q - 1);
		quickSort(A, q + 1, right);
	}
}


int partition(int A[], int left, int right)
{
	int low = left;
	int high = right + 1;
	int pivot = A[left];

	do {
		do {
			low++;
		} while (low <= right && A[low] < pivot);
			do {
				high--;
			} while (left <= high && A[high] > pivot);
			if (low < high)
				swap(A[low], A[high]);
	} while (low < high);
	
	swap(A[left], A[high]);
	return high;
}

simm4256 6년 전 0

일반적인 정렬로 풀 수 있는 문제가 아닙니다만...

출제자가 의도 한건진 모르겠지만 sort 함수를 사용하면 아슬아슬하게 AC가 뜹니다.

물론 sort 함수에 필적할 정도로 (혹은 그 이상으로) 최적화된 정렬을 사용해도 됩니다.

정해가 궁금하시다면

Quick Select 에 대해 찾아보세요.

kyhdudgns113 6년 전 0

퀵소트 같은 경우는 보통의 경우에서는 매우 좋은 성능을 보이지만, 최악의 경우는 선택정렬등과 같은 성능을 보입니다.

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

문제

문제

출처

ICPC

시간초과 문제

hwider 6년 전 0

simm4256 6년 전 0

kyhdudgns113 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말