[24/11/30] 머지소트 & 빠른 출력

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n =Integer.parseInt(st.nextToken());
      int[] arr= new int[n];
      for(int i=0; i<n; i++){
        st = new StringTokenizer(br.readLine());
        arr[i]=Integer.parseInt(st.nextToken());
      }
      mergeSort(arr,0,arr.length-1);
      for(int i=0; i<arr.length; i++){
        bw.write(arr[i]+"\n");
      }
      bw.flush();
      bw.close();

  }
  public static void mergeSort(int[] arr, int start, int end){
    if(start==end){
      return;
    }
    
    int[] temp = new int[end-start+1];
    
    int s1 = start;
    int mid = (start+end)/2;
    int s2 = mid+1;
    int index =0;
    
    mergeSort(arr,s1,mid);
    mergeSort(arr,mid+1,end);
    
    //투포인터
    while(s1<=mid && s2<=end){
      if(arr[s1]>arr[s2]){
        temp[index++]=arr[s2++];
      }
      else {
        temp[index++]=arr[s1++];
      }
    }
    if(s1>mid){
      while(s2<=end){
        temp[index++]=arr[s2++];
      }
    }
    else if(s2>end){
      while(s1<=mid){
        temp[index++]=arr[s1++];
      }
    }
    int copyIndex = start;
    for(int i=0; i<temp.length; i++){
      arr[copyIndex++]=temp[i];
    }
  }
  

  
}

 

마찬가지로 머지소트 썼다.

퀵소트의 경우 평범하면 O(nlogn)이지만 최악의 경우 O(n^2) 인데 N 값이 1000000이니까 O(n^2)은 안될거같아서 

고정 O(nlogn)의 머지소트를 사용했다.

 

문제는 머지소트를 빠른 입력만 쓰고 출력은 System.out.print로 뽑았더니 타입아웃이 걸렸다.

O(nlogn)일때 머지소트는 2천만번 연산을 일단 가져간다. 

시간이 2초니까 2억번까지는 가능한데 타임아웃이 나길래 의아했다.

 

Arrays.sort()

배열을 sort 할땐  dual-pivot Quicksort 로 퀵소트를 사용한다. 그래서 평균 시간복잡도는 O(nlogn)이지만 최악의 경우 O(n^2)인건 동일하다. 따라서 일단 얘는 안될거같고....

 

Collections.sort()

이건 처음 알았다. TimSort 방법을 사용하고 합병 및 삽입정렬을 사용한다고 한다. hybrid sorting algorithm.

이 알고리즘은 O(n) ~ O(nlogn) 임을 보장한다. 단점은 결국 Collections 타입으로 만들고 정렬해야하긴 한다.

 

나는 일단 머지소트로 구현하고 연산 줄일곳을 찾아봤다. 그 결과 출력쪽에서 빠른출력을 사용하여 시간을 줄여볼려했다.

1) BufferedWriter , sout 말고 더 빠르게 출력+ 버퍼에 모아놨다가 한번에 출력

2) StringBuilder , 한번에 하나씩 sout 하는게 아니라 버퍼에 모아놨다가 한번에 sout 하기.