글 읽기 - 시간초과인데 더 빠르게 푸는법

minu0122 5년 전 1

c++로 구현했는데 scanf 하고 printf 가 cin 이나 cout 보다 빠르다고 해서 c 라이브러리 추가해서 사용했습니다. 또한 정렬할때 quicksort로 했는데 시간초과가 뜨길래 quicksort의 최악의 경우를 넣은건가 싶어서 mergesort로 바꾸었는데 아직도 시간초과가 뜹니다. 혹시 조언좀 구할 수 있을까요?

#include <stdio.h>
#include <stdlib.h>

void merge(int *, int, int, int);
void mergesort(int *, int, int);

int main()
{
	int n, k, *num, i;
	scanf("%d %d", &n, &k);
	num = new int[n];
	for (i = 0; i < n; i++)
		scanf("%d", &num[i]);
	mergesort(num, 0, n - 1);
	printf("%d", num[k - 1]);
}

void merge(int *num, int l, int m, int r)
{
	int i, j, k;
	int n1 = m - l + 1, n2 = r - m;
	int *L, *R;
	L = new int[n1];
	R = new int[n2];
	for (i = 0; i < n1; i++)
		L[i] = num[l + i];
	for (j = 0; j < n2; j++)
		R[j] = num[m + 1 + j];
	i = 0;
	j = 0;
	k = l;
	while (i < n1 && j < n2)
	{
		if (L[i] <= R[j])
		{
			num[k] = L[i];
			i++;
		}
		else
		{
			num[k] = R[j];
			j++;
		}
		k++;
	}
	while (i < n1)
	{
		num[k] = L[i];
		i++;
		k++;
	}
	while (j < n2)
	{
		num[k] = R[j];
		j++;
		k++;
	}
	delete[] L;
	delete[] R;
}

void mergesort(int *num, int l, int r)
{
	if (l < r)
	{
		int m = l + (r - l) / 2; 
		mergesort(num, l, m);
		mergesort(num, m + 1, r);
		merge(num, l, m, r);
	}
}

djm03178 5년 전 0

질문을 올릴 때 위에 읽으라고 나오는 공지사항을 읽으셨나요? 그 글에 굵은 글씨로 적힌 문장을 다시 읽어보시기 바랍니다.

chogahui05 5년 전 0

더 빠르게 하는 방법

: new랑 delete를 안 쓰면 됩니다.

사실 그냥 L과 R을 전역변수처럼 써 버리면 더 빨라지겠죠. 할당할 필요도 없으니까.

sort 함수를 쓴 경우, 1.5초 정도에 아슬아슬하게 통과했다는 것만 참고하심 됩니다.

그리고

(1) 할당

(2) 복사

(3) merge

(4) 제거

에서 사실상 (1), (4)는 필요가 없죠.

chogahui05 5년 전 0

O(nlogn)짜리인데, 아슬아슬하게 통과하는 경우

상수를 낮추는 것도 중요해요.

minu0122 5년 전 0

djm03178님 게시판에서 mergesort를 찾아봤다고 생각했는데 착각이었네요;; 앞으로 좀더 샅샅이 찾아보겠습니다

chogahui05님 조언 감사합니다

minu0122 5년 전 0

chogahui05님 말씀하신대로 sort도 써보고 직접 quicksort 만들어서 k 값이 있는쪽으로 정렬하는 코드를 만들었는데 결과는 똑같네요ㅠㅠ

혹시 제 코드를 보시고 또 조언이 생각나셔서 댓글 달아주시면 정말 감사하겠습니다

#include <iostream>
#include <algorithm>

using namespace std;

int num[5000000];

int main()
{
	int n, k, i = 0;
	scanf("%d %d", &n, &k);
	for (i; i < n; i++)
		scanf("%d", &num[i]);
	sort(num, num + n);
	printf("%d", num[k - 1]);
}//sort사용





#include <stdio.h>

int tmp, pivot, i;

int num[5000000];

void quicksort(int num[], int l, int r, int k)
{
	if (l < r)
	{
		pivot = num[r];
		i = (l - 1);
		for (int j = l; j <= r - 1; j++)
		{
			if (num[j] <= pivot)
			{
				i++;
				tmp = num[i];
				num[i] = num[j];
				num[j] = tmp;
			}
		}
		tmp = num[i + 1];
		num[i + 1] = num[r];
		num[r] = num[i + 1];
		if (k < i + 1)
			quicksort(num, l, i, k);
		if (k > i + 1)
			quicksort(num, i + 2, r, k);
	}
}
int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%d", &num[i]);
	quicksort(num, 0, n - 1, k - 1);
	printf("%d", num[k - 1]);
}//k-1번째 값 쪽으로 quicksort