글 읽기 - 자바 합병절령로는 시간초과가 날수 밖에 없나요?

hwahn416 3년 전 0

합병정렬로 푸니까 시간초과가 나네요..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static int[] a;
	public static int[] tmp;
	
	public static void mergeSort(int[] a, int[] tmp,int start,int end) {
		if(start<end) {
			int mid = (start+end)/2;
			mergeSort(a,tmp,start,mid);
			mergeSort(a,tmp,mid+1,end);
			merge(a,tmp,start,mid,end);
		}
	}
	public static void merge(int[] a,int[] tmp,int start, int mid,int end) {
		for(int i=start;i<=end;i++) {
			tmp[i]=a[i];
		}
		
		int part1 = start;
		int part2 = mid+1;
		int index = start;
		
		while(part1<=mid&&part2<=end) {
			if(tmp[part1]<=tmp[part2]) {
				a[index]=tmp[part1];
				part1++;
			}
			else {
				a[index]=tmp[part2];
				part2++;
			}
			index++;
		}
		for(int i=0;i<mid-part1+1;i++) {
			a[index+i]=tmp[part1+i];
		}
	}

	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());
		a= new int[N];
		tmp = new int[N];
		for(int i=0;i<N;i++) {
			a[i]=Integer.parseInt(br.readLine());
		}
		mergeSort(a,tmp,0,a.length-1);
		for(int i=0;i<a.length;i++) {
			bw.write(Integer.toString(a[i])+"\n");
		}
		bw.close();
	}

}

otter66 3년 전 1

뭔가 답을 알려드리는 것 같아서 돌려서 말씀드릴게요.

(퀵정렬, 병합정렬보다 빠른)가장 빠른 정렬 알고리즘을 사용하시면 됩니다.

shg9411 3년 전 2

문제 조건과 범위를 다시 읽어보시면 도움이 될 것 같습니다.

hwahn416 3년 전 0

감사합니다! 카운팅정렬로 풀어보니 정답이 나오네요

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

문제

문제

출처

ICPC

자바 합병절령로는 시간초과가 날수 밖에 없나요?

hwahn416 3년 전 0

otter66 3년 전 1

shg9411 3년 전 2

hwahn416 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말