글 읽기 - 머지소트 시간초가해결방법 알고 싶습니다...! (java)

thfdldl 6년 전 0

머지소트를 보통 재귀호출로 짜는것으로 알고 있습니다.

잘 돌가는거 같은데 시간초가가 뜸니다..

시간초가 문제는 어떻게 해결해야하나요..ㅠㅠ

이중 반복문을 쓴 것도 아닌데 어떻게 하면 더 시간을 줄일수 있을지 궁금합니다!!

import java.io.*;
import java.util.*;

public class Main {
	void mergesort(int arr[], int left, int right){
		if(right <= left) return ;
		
		int mid = (left + right)/2;
		mergesort(arr, left, mid);
		mergesort(arr, mid+1, right);
		merge(arr,left,mid,right);
	}

	void merge(int[] arr, int left, int mid, int right) {
		int resultArr[] = new int[arr.length];
		int i, j, k, t;
		i = left;
		j = mid + 1;
		k = left;
		
		while (i <= mid && j <= right) {
			if (arr[i] <= arr[j])
				resultArr[k] = arr[i++];
			else
				resultArr[k] = arr[j++];
			k++;
		}
		
		if (i > mid) {
			for (t = j; t <= right; t++, k++)
				resultArr[k] = arr[t];
		} else {
			for (t = i; t <= mid; t++, k++)
				resultArr[k] = arr[t];
		}
		for (t = left; t <= right; t++)
			arr[t] = resultArr[t];
	}
	
	public static void main(String[] args) throws IOException{
		Main m = new Main();
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		
        int N = Integer.parseInt(f.readLine());  
		int arr[] = new int[N];
		
		for(int i=0; i<arr.length; i++){
			arr[i] = Integer.parseInt(f.readLine());  
		}
		
		m.mergesort(arr, 0, arr.length-1);
		
		for(int num : arr){
			out.println(num);
		}
		out.close();
	}
}

toysmars 6년 전 0

merge()가 호출될때마다 배열을 새로 할당하는게 문제일까요?

chogahui05 6년 전 0

네. 배열의 최대 크기가 100만인데

merge가 호출이 될 때마다 새로 100만짜리 배열을 할당하면.. 음.. 일단 4byte짜리 변수 배열을 할당했다고 한다면..

100만 * 4byte = 4Mbyte네요.

가비지 콜렉터의 minor gc와 major gc를 구글링 해 보시는 거 추천드립니다.

gc 작업은 생각보다 무거운 작업입니다. gc 작업을 할 때는 오로지 gc만 수행해야 하는 것도 있고요.

알고리즘도 그렇게 간단치는 않습니다.

예를 들어, 운영체제나 프로그래밍 언어 시간에 배우는 mark & sweep 알고리즘의 경우에는

(1) 모든 객체를 조사합니다.

(2) unreachble한 것을 조사합니다. root로부터.

https://www.hboehm.info/gc/com...

chogahui05 6년 전 0

그냥 메인이나, 아니면 merge sort를 수행하게 하기 위한 함수를 따로 만들어서

거기에서 resultarr 배열을 만들고

merge 함수를 호출할 때 resultarr 배열을 (어짜피 주소값을 저장하니까 값복사로 넘겨도 상관 없겠죠..)

값복사 하는 식으로 넘기면 될 듯 싶네요. 알고리즘 자체는 맞습니다.

void do_merge(int[] arr, int n)
{
    int resultArr[] = new int[arr.length];
    int left=0,right=n-1;
    merge(arr,resultArr,left,(left+right)>>1,right);
}

thfdldl 6년 전 0

정말 감사합니다. 통과됐네요 드디어ㅠㅠ!!

많이 배워갑니다!!

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

문제

문제

출처

ICPC

머지소트 시간초가해결방법 알고 싶습니다...! (java)

thfdldl 6년 전 0

toysmars 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

thfdldl 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말