글 읽기 - C언어 시간 초과 질문드립니다.

wkdgusrb3 4년 전 0

어디서 시간을 줄일수 있을까요? 정렬 과정에서도 머지정렬을 써서 더 빠르게 할수는 없을거 같은데 계속 시간 초과가 뜨네요

#include<stdio.h>
#include<stdlib.h>
int a[500001], b[500001];
void mergesort(int left, int mid, int right) {
	int i, j, k;
	i = left; j = 0; k = mid + 1;
	while (i <= mid && k <= right) {
		if (a[i] < a[k]) {
			b[j++] = a[i++];
		}
		else {
			b[j++] = a[k++];
		}
	}
	while (i <= mid) {
		b[j++] = a[i++];
	}
	while (k <= right) {
		b[j++] = a[k++];
	}
	for (i = 0; i < j; i++) {
		a[i + left] = b[i];
	}


}
void merge(int left,int right) {
	int mid;
	if (left < right) {
		mid = (left + right) / 2;
		merge(left, mid);
		merge(mid + 1, right);
		mergesort(left,mid,right);
	}
}
int main(void) {
	int i, j, k, number,cf=0, max, min, f = 0, count = 0, mn = 0,fc=0;
	int middle;
	float sum = 0.0f;
	scanf_s("%d", &number);
	for (i = 0; i < number; i++) {//평균 및 최대, 최소값 구하기
		scanf_s("%d", &j);
		if (i == 0) {
			max = min = j;
		}
		sum += j;
		a[i] = j;
		if (max < j) {
			max = j;
		}
		else if (min > j) {
			min = j;
		}
	}
	merge(0,number-1);//merge sort
	for (i = 0; i < number; i++) {//최빈수 구하기
		count = 0;
		for (j = i; j < number; j++) {
			if (a[i] == a[j]) {
				count++;
			}
		}
		if (count > f) {
			mn = a[i];
			f = count;
			k = 1;
		}
		else if (count == f&&k) {
			mn = a[i];
			k = 0;
		}
		

	}
	sum /= number;
	middle = (number - 1) / 2;
	printf("%.0f\n%d\n%d\n%d",sum,a[middle],mn,max-min);
	return 0;
}

bupjae 4년 전 1

56~74 번째 줄의 반복문의 시간복잡도가 O(n^2) 입니다. 최빈값을 구하는 다른 방법을 생각하셔야 합니다.

wkdgusrb3 4년 전 0

감사합니다ㅠㅠㅠ

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

문제

문제

출처

ICPC

C언어 시간 초과 질문드립니다.

wkdgusrb3 4년 전 0

bupjae 4년 전 1

wkdgusrb3 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말