글 읽기 - 자바) 합병정렬 시간초과

2jaebbaang 3년 전 0

병합정렬을 이용했는데 왜 계속 시간초과가 뜨는지 이유를 모르겠습니다.

import java.util.*;
import java.io.*;
public class Main {
	
	public static void merge(int[] A, int left, int mid, int right) {
		int i=left;
		int j=mid+1;
		int[] temp= new int[A.length];
		int k=0;
		while(i<=mid && j<=right) {
			if(A[i]<=A[j]) {
				temp[k]=A[i];
				i++;
				k++;
			}
			else {
				temp[k]=A[j];
				j++;
				k++;
			}
		}
		
		while(i<=mid) {
			temp[k]=A[i];
			i++;
			k++;
		}
		while(j<=right) {
			temp[k]=A[j];
			j++;
			k++;
		}
		k--;
		for(int l=0; l<=k; l++) {
			A[left+l]=temp[l];
		}
	}
	
	public static void mergesort(int[] A, int left, int right) {
		if(left<right) {
			int mid = (left+right)/2;
			mergesort(A, left, mid);
			mergesort(A, mid+1, right);
			merge(A, left, mid, right);
		}
		else
			return;
	}
    
    	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] arr= new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		mergesort(arr,0,arr.length-1);
		for(int i=0; i<n; i++) {
			bw.write(Integer.toString(arr[i])+"\n");
		}
		bw.flush();
		bw.close();
		}
}

djm03178 3년 전 3

new int[A.length]; 를 매번 수행하면 O(N)번의 호출 시마다 크기가 O(N)인 배열을 할당받게 되므로 총 O(N^2) 시간이 걸립니다. end - start + 1만큼만 할당받거나, 아니면 할당을 미리 하나만 받아두고 재사용해야 합니다.

2jaebbaang 3년 전 0

퀵정렬로 푼건데요. 이것도 시간초과가 뜹니다. 전혀 모르겠어요 ㅠㅠ

import java.util.*;
import java.io.*;
public class Main {
	
	
	static void quicksort(int[] A, int start, int end) {
		if(start<end) {
			int index=partition(A,start,end);
			quicksort(A,start,index-1);
			quicksort(A,index+1,end);
		}
		else
			return;
	}
	
	static int partition(int[] A, int start, int end) {
		int pivot = A[start];
		int temp;
		while(start<end) {
			while(A[start]<pivot && start<end)
				start++;
			while(A[end]>pivot && start<end)
				end--;
			
			if(start<end) {
				temp=A[start];
				A[start]=A[end];
				A[end]=temp;
			}
		}
		return start;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] arr= new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		quicksort(arr,0,arr.length-1);
		for(int i=0; i<n; i++) {
			bw.write(Integer.toString(arr[i])+"\n");
		}
		bw.flush();
		bw.close();
		}
}

djm03178 3년 전 1

처음부터 이걸 드릴 걸 그랬습니다.

https://www.acmicpc.net/board/...

2jaebbaang 3년 전 0

감사합니다. 정말 큰 도움됐습니다!

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

문제

문제

출처

ICPC

자바) 합병정렬 시간초과

2jaebbaang 3년 전 0

djm03178 3년 전 3

2jaebbaang 3년 전 0

djm03178 3년 전 1

2jaebbaang 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말