글 읽기 - [JAVA] 시간초과 ...

mae0428 4년 전 0

병합정렬을 이용해서 문제를 풀려고 했는데 계속 시간초과가 뜨네요... ㅠㅠ

어느 부분에서 시간초과가 일어나는 걸까요??

import java.util.*;

/* 수 정렬하기 2 */
public class Main {
	static int sorted[]=new int[1000000];
	
	public static void mergeSort(int arr[], int start, int end) {
		if(start<end) {
			int mid=(start+end)/2;
			mergeSort(arr,start,mid);
			mergeSort(arr,mid+1,end);
			merge(arr,start,mid,end);
		}
	}
	public static void merge(int arr[], int start, int mid, int end) {
		int part1=start; // 첫번째 나누어진 배열 시작 부분
		int part2=mid+1; // 두번째 나누어진 배열 시작 부분
		int index=start;
		while(part1<=mid && part2<=end) {
			if(arr[part1]<=arr[part2]) {
				sorted[index]=arr[part1];
				part1++;
			} else {
				sorted[index]=arr[part2];
				part2++;
			}
			index++;
		}
        // 뒤쪽 배열이 남은 경우
		if(part1>mid) {
			for(int i=part2;i<=end;i++) {
				sorted[index]=arr[i];
				index++;
			}
		} else { // 앞쪽 배열이 남은 경우
			for(int i=part1;i<=mid;i++) {
				sorted[index]=arr[i];
				index++;
			}
		}
        // 정렬된 배열을 원래 배열에 다시 저장
		for(int i=start;i<=end;i++) {
			arr[i]=sorted[i];
		}
	}
	public static void printArr(int arr[]) {
		for(int i=0;i<arr.length;i++) {
			System.out.println(arr[i]);
		}
	}

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int num=scanner.nextInt();
		int arr[]=new int[num];
		for(int i=0;i<arr.length;i++) {
			arr[i]=scanner.nextInt();
		}
		mergeSort(arr,0,arr.length-1);
		printArr(arr);
		scanner.close();
	}
}

djm03178 4년 전 1

https://www.acmicpc.net/blog/v...

mae0428 4년 전 0

앗 감사합니당!!!!!!! 해결했습니당!!!

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

문제

문제

출처

ICPC

[JAVA] 시간초과 ...

mae0428 4년 전 0

djm03178 4년 전 1

mae0428 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말