글 읽기 - [java] 병합정렬 시간 초과 도와주세요..!

myyouthisyours 5년 전 0

시간 초과 나는 이유가 무엇일까요? ㅠㅠ

import java.io.*;

public class Main {
	
	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[] list = new int[N];
		
		for(int i = 0; i < N; i++) {
			
			list[i] = Integer.parseInt(br.readLine());
		}
		
		mergeSort(list, 0, N - 1);
		
		for(int i = 0; i < N; i++) {
			
			bw.write(String.valueOf(list[i]));
			bw.newLine();
		}
		
		bw.flush();
		br.close();
		bw.close();
	}
	
	static void mergeSort(int arr[], int l, int r) {
		
		int m;
		
		if(l < r) {
			
			m = (l + r) / 2;
			
			mergeSort(arr, l, m);
			mergeSort(arr, m+1, r);
			merge(arr, l, m, r);
			
		}
		
	}
	
	static void merge(int arr[], int l, int m, int r) {
		
		int[] sorted = new int[arr.length];
		
		int i = l;
		int j = m + 1;
		
		int k = l;
		
		while(i <= m && j <= r) {
			
			if(arr[i] <= arr[j]) {
				
				sorted[k] = arr[i];
				i++;
			} else {
				sorted[k] = arr[j];
				j++;
			}
			k++;
		}
		
		if(i > m) {
			
			for(int a = j; a <= r; a++, k++) {
				
				sorted[k] = arr[a];
			}
		} else {
			
			for(int a = i; a <= m; a++, k++) {
				
				sorted[k] = arr[a];
			}
		}
		
		for(int a = l; a <= r; a++) {
			
			arr[a] = sorted[a];
		}
	}
	
}

djm03178 5년 전 0

50번째 줄처럼 매번 arr의 크기만큼의 배열을 새로 할당하면 merge 함수가 호출될 때마다 원소의 수에 비례하는 시간이 걸리게 됩니다. 그래서 총 시간복잡도가 O(N^2)이 됩니다.

myyouthisyours 5년 전 0

클래스 변수로 선언해서 해결했습니다. 감사합니다.

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

문제

문제

출처

ICPC

[java] 병합정렬 시간 초과 도와주세요..!

myyouthisyours 5년 전 0

djm03178 5년 전 0

myyouthisyours 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말