백준 정렬 - 2751번 : 수 정렬하기

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

---

O(nlogn)의 정렬 방식을 이용하여 정렬을 수행해야 하는 문제이다.

나는 항상 O(nlogn)의 시간 복잡도를 가지는 병합정렬을 이용해서 문제를 풀었는데, 계속 시간초과가 발생했다.

질문 게시판을 보며 뭐가 문제일까 봤는데 주로 문제가 되는 배열 할당이나 배열을 옮겨적는 과정에서 발생하는 시간 문제로 인해 O(N^2)이 되는 문제는 나한테 해당이 되지 않았다. 그래서 알아보던 중 출력속도도 시간초과에 영향이 있다는 것을 알게되었다. C++의 endl이나 cout, cin 등은 굉장히 느리다는 것은 알고 있었지만 java의 System.out.prinln()도 굉장히 느린 것을 알게되었다. 

새로 알게된 BufferedWriter를 이용해서 출력을 수행하니 통과가 되었다.

출력함수별 속도를 측정해놓은 게시글을 확인하니 System.out.prinln()보다 약 30배는 빠르다고 한다.

import java.util.*;
import java.io.*;
public class Main {
	public static int[] sorted;
	public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i=0; i<n; i++){
            a[i] = sc.nextInt();
        }
        sorted = new int[n];
        merge_sort(a,0,n-1);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<sorted.length; i++) {bw.write(a[i]+"\n");}
        bw.close();
    }
	public static void merge_sort(int[] a, int i, int j) {
		if(i==j) return;
		int mid = (i+j)/2;
		merge_sort(a,i,mid);
		merge_sort(a,mid+1,j);
		merge(a,i,mid,j);
	}
	public static void merge(int[] a,int i, int mid, int j) {
		int idx = i;
		int start = i;
		int target = mid+1;
		while(start<=mid&&target<=j) {
			if(a[start]<=a[target]) {
				sorted[idx++] = a[start];
				start++;
			}
			else if(a[start]>a[target]){
				sorted[idx++] = a[target];
				target++;
			}
		}
		
		while(start<=mid) {
			sorted[idx++] = a[start];
			start++;
		}
		while(target<=j) {
			sorted[idx++] = a[target];
			target++;
		}
		for(int k = i; k<=j; k++) {
			a[k] = sorted[k]; 
		}
	}
}