글 읽기 - 1448 시간초과 문제, Stackoverflow [C]

stevenkim310 1년 전 0

빠른정렬 기준으로 배열 정렬해서 시간초과를 해결하려고 했는데 Stack overflow가 발생하는 이유가 뭘까요?...

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int arr[1000001];

int  Partition(int arr[], int L, int R)
{
	int left = L;
	int right = R;
	int pivot = arr[(left + right) / 2];
	while (left < right)
	{
		while (arr[left] < pivot)
			left++;
		while (arr[right] > pivot)
			right--;
		if (left < right)
		{
			int temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
			left++;
			right--;
		}
	}
	if (left == right)
		right--;
	return left;
}
void quickSort(int arr[], int L, int R)
{
	int left = Partition(arr, L, R);
	int right = left + 1;
	if (L < right)
		quickSort(arr, L, right);
	if (left < R)
		quickSort(arr, left, R);
}

int main(void)
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	quickSort(arr, 0, n - 1);
	for (int i = n-3; i >=0; i--) 
	{
		if (arr[i+2] < arr[i+1] + arr[i])
		{
			printf("%d", arr[i] + arr[i + 1] + arr[i + 2]);
			break;
		}
		if (i == 0)
			printf("%d", -1);
	}
	return 0;
}

djm03178 1년 전 1

퀵정렬은 최악의 경우 O(N^2)입니다. 이름과 달리 전혀 빠르지 않습니다. 병합 정렬이나 힙 정렬, 또는 그냥 라이브러리 함수를 사용해야 합니다.

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

문제

문제

출처

ICPC

1448 시간초과 문제, Stackoverflow [C]

stevenkim310 1년 전 0

djm03178 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말