글 읽기 - 시간초과가 왜 나는지 이해가 안되네요

domw324 8년 전 1

머지소트 사용했구요.

시간복잡도 계산해보니까 O(N*logN)해서 연산은 3천만번 정도 밖에 안되는데

시간초과가 뜨네요.

왜 그런지 이해가 안가구요.. 어떻게 바꾸면 좋을지 알려주시면 감사하겠습니다~

#include <cstdio>
#define ULLI long long int

int N, K;
ULLI arr[5000001];
ULLI temp[5000001];

void merge(int left, int right){
	int mid = (left + right) / 2;

	int fidx = left;
	int ridx = mid + 1;

	int index = 0;

	while (fidx <= mid && ridx <= right){
		if (arr[fidx] <= arr[ridx]){
			temp[index++] = arr[fidx++];
		}
		else{
			temp[index++] = arr[ridx++];
		}
	}

	while (fidx <= mid){
		temp[index++] = arr[fidx++];
	}
	while (ridx <= right){
		temp[index++] = arr[ridx++];
	}

	for (int i = left; i <= right; i++){
		arr[i] = temp[i - left];
	}
}

void merge_sort(int left, int right){
	if (left == right)
		return;

	int mid = (left + right) / 2;

	merge_sort(left, mid);
	merge_sort(mid + 1, right);

	merge(left, right);
}

int main(){

	scanf("%d %d", &N, &K);

	for (int i = 0; i < N; i++){
		scanf("%lld", &arr[i]);
	}

	merge_sort(0, N - 1);
	
	printf("%lld\n", arr[K - 1]);

	return 0;
}

koosaga 8년 전 2

nlgn이면 1억 천만번 아닌가요?

5백만개 원소 정렬하는 건 1.5초안에 빡빡한 경우가 많아서 다른 방법을 생각하시는게 좋을 거 같습니다.

어림잡아 O(n) 정도에 되는 방법이 있어요.

koosaga 8년 전 1

힌트 : selection algorithm을 찾아보시거나, std::nth_element 에 대해서 찾아보시길...

indioindio 8년 전 2

이 문제가 파이썬처럼 한 줄을 통째로 입력받으면 라이브러리의 정렬을 사용해도 시간 내에 간신히 들어올 수 있지만

그렇지 않다면 시간 내에 들어오기가 어렵습니다. (방금해보니 c언어로 빠른 입력 함수 + 퀵 소트로도 안되네요.)

퀵소트의 매 함수 호출마다 한 원소의 자리가 정해진다는 특성을 사용하셔야 할 것 같습니다.

domw324 8년 전 1

koosaga님, indioindio님 감사합니다.

제가 시간복잡도 계산을 잘못했네요 ㅠㅠㅠ...

한번 다시 풀어볼게요~ 감사합니다

baactree 8년 전 4

크 500백만 nlogn = 3천만 기적의 수학에 좋아요 누르고 갑니다.

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

문제

문제

출처

ICPC

시간초과가 왜 나는지 이해가 안되네요

domw324 8년 전 1

koosaga 8년 전 2

koosaga 8년 전 1

indioindio 8년 전 2

domw324 8년 전 1

baactree 8년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말