글 읽기 - [c언어]시간 초과 한번만 봐주세요

whdqor00 4년 전 0

c언어로 구현한 소스코드입니다. 제가 쉬운 코드를 너무 풀어쓴건지 계속 시간초과가 뜹니다. 어디서 뜨는지 감이 안 잡히는데 한번만 도움 부탁드리겠습니다.

#include <stdio.h>
#include <math.h>

int main(void)
{
	int n;
	scanf("%d", &n);

	int arr[500001], arr1[500001];

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

	//산술평균
	int add = 0;

	for (int i = 0; i < n; i++)
	{
		add += arr[i];
	}

	double avg;

	avg = (double)add / n;
	avg = round(avg);

	printf("%d\n", (int)avg);


	//중앙값
	arr1[0] = arr[0];

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr1[j] == arr[i])
			{
				for (int k = i; k >= j + 2; k--)
				{
					arr1[k] = arr1[k - 1];
				}
				arr1[j + 1] = arr[i];
				break;
			}
			if (arr1[0] > arr[i])
			{
				for (int k = i - 1; k >= 0; k--)
				{
					arr1[k + 1] = arr1[k];
				}
				arr1[0] = arr[i];
			}
			if (arr1[j]<arr[i] && arr1[j + 1]>arr[i])
			{
				for (int k = i; k >= j + 2; k--)
				{
					arr1[k] = arr1[k - 1];
				}
				arr1[j + 1] = arr[i];
				break;
			}
			if (arr[i] > arr1[i - 1])
			{
				arr1[i] = arr[i];
			}
		}
	}

	if (n == 1)
	{
		printf("%d\n", arr[0]);
	}
	else
	{
		printf("%d\n", arr1[n / 2]);
	}

	//최빈값
	int arr2[8001];
	for (int i = 0; i < 8001; i++)
	{
		arr2[i] = 0;
	}

	for (int i = 0; i < n; i++)
	{
		arr2[arr[i] + 4000]++;
	}

	int max = arr2[0];
	for (int i = 1; i < 8001; i++)
	{
		if (arr2[i] > max)
		{
			max = arr2[i];
		}
	}

	int cnt = 0;

	if (n == 1)
	{
		printf("%d\n", arr[0]);
	}
	else
	{
		for (int i = 0; i < 8001; i++)
		{
			if (arr2[i] == max)
			{
				cnt++;
				if (cnt == 2)
				{
					printf("%d\n", i - 4000);
					break;
				}
			}
		}

		if (cnt == 1)
		{
			for (int j = 0; j < 8001; j++)
			{
				if (arr2[j] == max)
				{
					printf("%d\n", j - 4000);
					break;
				}
			}
		}
	}

	//범위
	int max1 = arr[0];
	int min1 = arr[0];

	for (int i = 1; i < n; i++)
	{
		if (arr[i] > max1)
		{
			max1 = arr[i];
		}
		if (arr[i] < min1)
		{
			min1 = arr[i];
		}
	}

	printf("%d\n", max1 - min1);

	return 0;
}

bupjae 4년 전 0

중앙값 구하는 알고리즘이 O(n^3) 인 것으로 보입니다.

문제에서 요구하는 입력 데이터의 크기를 고려했을 때 중앙값은 적어도 O(n log n) 만에 구할 수 있어야 합니다.

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

문제

문제

출처

ICPC

[c언어]시간 초과 한번만 봐주세요

whdqor00 4년 전 0

bupjae 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말