글 읽기 - 시간초과...이거 시간복잡도가 어떻게 되나요?

zjtlfk 1년 전 0

문제에서 의도한 방향이 아닌 것 같지만 합병정렬로 구현해보았습니다..

예제나 반례들을 돌렸을 때는 잘 돌아가는데, 제출을 해보니 시간초과가 발생하네요

값을 삽입할때마다 합병정렬을 실행하는데 이거 때문에 시간초과가 발생하는걸까요?

혹시 시간복잡도 때문이라면 이 코드의 시간복잡도를 설명해주시면 감사하겠습니다

#include<stdio.h>

void merge(int a[], int s, int m, int e) //합병정렬
{
	int count = 0;
	int* tmp = (int*)malloc(sizeof(int) * (e - s + 1));
	int left = s;
	int right = m + 1;
	while ((left <= m) && (right <= e))
	{
		if (a[left] == a[right])
		{
			if (a[left] < a[right])
				tmp[count++] = a[left++];
			else
				tmp[count++] = a[right++];
		}
		else if (a[left] < a[right])
			tmp[count++] = a[left++];
		else
			tmp[count++] = a[right++];
	}
	while (left <= m)
		tmp[count++] = a[left++];
	while (right <= e)
		tmp[count++] = a[right++];
	for (int i = 0; i < e - s + 1; i++)
		a[s + i] = tmp[i];
	free(tmp);
}
void mergesort(int a[], int s, int e)
{
	if (s < e)
	{
		int m = (s + e) / 2;
		mergesort(a, s, m);
		mergesort(a, m + 1, e);
		merge(a, s, m, e);
	}
}

int main(void)
{
	int t;
	scanf("%d", &t);
	int** result = (int**)malloc(sizeof(int*) * t);
	for (int i = 0; i < t; i++)
	{
		int k, min=0, max=0;
		scanf("%d", &k);
		int* arr = (int*)malloc(sizeof(int) * k);
		result[i] = (int*)malloc(sizeof(int) * 2);
		for (int j = 0; j < k; j++)
		{
			char ct;
			int in;
			scanf(" %c %d", &ct, &in);
			if (ct == 73)
			{
				arr[max++] = in;
				mergesort(arr, min, max - 1); 삽입시마다 합병정렬
			}
			else
			{
				if (min == max)
					continue;
				else if (in == -1)
					arr[min++] = 0;
				else
					arr[--max] = 0;
			}
		}
		if (min == max) //비었는지 확인
		{
			result[i][0] = 0;
			result[i][1] = 1;
		}
		else //안비었으면 최댓값 최솟값 결과에 넣기
		{
			result[i][0] = arr[max - 1];
			result[i][1] = arr[min];
		}
		free(arr);
	}
	for (int i = 0; i < t; i++)
	{
		if (result[i][0] < result[i][1])
			printf("EMPTY\n");
		else
			printf("%d %d\n", result[i][0], result[i][1]);
	}
	return 0;
}

bnb2011 1년 전 0

큐에 값을 삽입하는 연산의 횟수가 O(Q)번이고, Merge Sort는 O(NlogN)의 시간이 걸리기 때문에 작성하신 코드의 시간 복잡도는 O(QNlogN)이 됩니다.

zjtlfk 1년 전 0

그럼 merge sort 로는 무조건 시간초과가 발생할 수 밖에 없는 건가요?

bnb2011 1년 전 1

네, 매 쿼리마다 Merge Sort를 수행하는 방식으로는 이 문제를 해결하기 어렵습니다.

이 문제는 삽입 삭제 연산이 적당히 빠르게 이루어져야 하며, 최댓값과 최솟값 또한 빠르게 구할 수 있는 자료구조를 구현하는 것이 문제의 의도입니다.

zjtlfk 1년 전 0

제가 너무 깊게 생각을 안해본것 같네요..

알려주셔서 감사합니다

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

문제

문제

출처

ICPC

시간초과...이거 시간복잡도가 어떻게 되나요?

zjtlfk 1년 전 0

bnb2011 1년 전 0

zjtlfk 1년 전 0

bnb2011 1년 전 1

zjtlfk 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말