글 읽기 - 이미 sort가 되어있으니까

johyesong8686 3년 전 0

sort를 할 필요가 없이 merge만 이용하면 된다는 것을 인지 했습니다

merge로하면 통과되는데 mergesort를쓰면 시간 초과가 나더라구요

mergesort 자체가 시간복잡도가 O(log*n)인데,

mergesort로 하면 왜 시간 초과가 나나요 ?

//merge 코드 
#include <iostream>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAX 10000001
using namespace std;


int ans[MAX];
int a[MAX];
int b[MAX];
int n,m;
void merge(){
	int i=0;
	int j=0;
	int k=0;
	while(i<n && j<m){
		if(a[i] <=b[j])
			ans[k++]=a[i++];
		else
			ans[k++]=b[j++];
		
	}	
	while(i<n)ans[k++]=a[i++];
	while(j<m) ans[k++]=b[j++];
	
	
}

int main(void) {

	cin >>n >>m;
	for(int i=0; i<n;i++){
		
		scanf("%d",&a[i]);
	
	}
	for(int i=0; i<m;i++){
		
		scanf("%d",&b[i]);
	
	}

	merge();
	
	for(int i=0; i<n+m;i++){
		printf("%d ",ans[i]);
	
	}
	
	


	return 0;
}
//mergeSort코드


#include <iostream>
#define MAX 10000001
//병합 정렬
//시간 복잡도 O(N*LOG(N ))
using namespace std;
int sorted[MAX];
int arr[MAX] ;

void merge(int a[], int middle, int m, int n) {

	int i = m;
	int j = middle + 1;
	int k = m;
	//작은 순서대로 배열 삽입
	while (i <= middle && j <= n) {
		if (a[i] <= a[j]) {

			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;

	}
	//남은 데이터도 삽입

	if (i > middle) {
		for (int t = j; t <= n; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else {
		for (int t = i; t <= middle; t++) {

			sorted[k] = a[t];
			k++;
		}
	}
	for (int t = m; t <= n; t++) {
		a[t] = sorted[t];

	}

}

void mergesort(int a[], int m, int n) {

	if (m < n) {

		int middle = (m + n) / 2;
		mergesort(a, m, middle);
		mergesort(a, middle + 1, n);
		merge(a, middle, m, n);
	}

}
int main(void) {
	int n, m;
	cin >>n >>m;
	for (int i = 0; i < n+m; i++) {

		cin >>arr[i];
	}


	
	mergesort(arr, 0, n+m - 1);
	for (int i = 0; i < n+m; i++) {

		printf("%d ", arr[i]);
	}








	return 0;
}

pichulia 3년 전 1

이 문제같은 경우는 log n 이 붙으면 치명적인 상황이기 때문입니다.

제출이력을 보니 O(n) 코드는 750ms 정도가 나오신걸로 추측되는데... 여기서 logn = 20 을 곱하면 약 15000 ms가 나올 것입니다. 1.5초 보다는 큰 시간이죠.

johyesong8686 3년 전 0

pichulia

감사합니다 ! 아직 코드 메모리 계산 하고 생각하는게 습관이 안되어있네요 !! ㅜㅜㅜ

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

문제

문제

출처

ICPC

이미 sort가 되어있으니까

johyesong8686 3년 전 0

pichulia 3년 전 1

johyesong8686 3년 전 0

pichulia

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말