글 읽기 - 자바 시간 초과 질문입니다(병합 정렬)

ygs3004 1년 전 0

시간초과가 나오는 이유를 모르겠습니다.

구글링과 질문들 찾아보며 수정했는데

어느부분때문에 시간초과가 나오는지 궁금합니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static long count=0;
	static int[] temp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[n];
		temp = new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		divide(arr, 0, n-1);
		System.out.println(count);
	}
	
	public static void divide(int[] arr, int start, int end) {
		if (end-start == 0) return;
			int mid = (start+end) / 2;
			divide(arr, start, mid);
			divide(arr, mid+1, end);
			
			merge(arr, start, end, mid);
			for(int i=start; i<=end; i++) {
				arr[i]=temp[i];
			}
	}
	
	public static void merge(int[] arr, int start, int end, int mid) {
						
		int tmpIndex = start;
		int left = start;
		int right = mid+1;
		
		while(left<=mid && right<=end) {
			if(arr[left]>arr[right]) {
				count += right - tmpIndex; 
				temp[tmpIndex++] = arr[right++];
			}else if(arr[right]>arr[left]) {
				temp[tmpIndex++] = arr[left++];
			}
		}
		
		while(left<=mid) {
			temp[tmpIndex++] = arr[left++];
		}
		
		while(right<=end) {
			temp[tmpIndex++] = arr[right++];
		}
		

	}
}

dldyddlwl 1년 전 1

	public static void merge(int[] arr, int start, int end, int mid) {
						
		int tmpIndex = start;
		int left = start;
		int right = mid+1;
		
		while(left<=mid && right<=end) {
			if(arr[left]>arr[right]) {            // 자, 아주 간단합니다. 자 left가 더 클 때!
				count += right - tmpIndex; 
				temp[tmpIndex++] = arr[right++];
			}else if(arr[right]>arr[left]) {        // 자, right가 더 클 때
				temp[tmpIndex++] = arr[left++];
			}                                    // 아니 잠깐, 그렇다면 left랑 right가 같을 때는요?!
		}                                            // left와 right가 증가할 수가 있을 까용?
        
        // 간단한 해법 : if와 else if가 아닌, if와 else로 처리하자!
		

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

문제

문제

출처

ICPC

자바 시간 초과 질문입니다(병합 정렬)

ygs3004 1년 전 0

dldyddlwl 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말