수 정렬하기 2

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

2751번: 수 정렬하기 2

// 코드 : 합병정렬 직접구현 -> 시간초과

import java.util.*;
import java.io.*;
 
public class Main{
  
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static int n;
  static int[] numbers;
  
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    n       = Integer.parseInt(st.nextToken());
    numbers = new int[n];
    
    
    for(int i=0; i<n; i++) {
      st      = new StringTokenizer(br.readLine());
      numbers[i] = Integer.parseInt(st.nextToken());  
    }
    
    // numbers를 0부터 n-1까지 정렬을 시킨다.
    mergeSort(0, n-1);
    
    // 정렬된 답을 출력한다.
    StringBuilder sb = new StringBuilder();
    for(int i=0; i<n; i++) {
      sb.append(numbers[i] + "\n");
    }
    bw.write(sb.toString());
    br.close();
    bw.flush();
    bw.close();
  }
  
  static void mergeSort(int start, int end) {
    
    if(start>=end) {
      return;
    } else {
      // 1.왼쪽 절반을 분할
      // 2.오른쪽 절반을 분할
      // 3.합친다.
      int mid = (start + end) / 2;
      mergeSort(start, mid);
      mergeSort(mid+1, end);
      
      // numbers[start ~ mid], numbers[mid+1 ~ end]는 이미 정렬이 되어 있음
      // 왼쪽, 오른쪽을 하나로 합친다.
      merging(start, mid, mid+1, end);
      
    }
    
  }
  
  // s1 ~ e2 : 이 둘을 합쳐서 정렬된 결과를 만드는 함수.
  static void merging(int s1, int e1, int s2, int e2) {
    int p=s1, q=s2; // p와 q의 현재 왼쪽, 오른쪽의 최솟값을 가르키는 변수들.
    int[] temp  = new int[n+1]; // 합쳐진 결과를 저장하는 임시 변수
    int tempIdx = 0;
    
    while(p<=e1 && q<=e2) {
      if(numbers[p]<=numbers[q]) {
        temp[tempIdx++] = numbers[p];  
        p++;
      } else {
        temp[tempIdx++] = numbers[q];
        q++;
      }
    }
    
    if(p>e1) { //p가 나갔다...q에 원소가 남았다.
      for(int i=q; i<=e2; i++) {
        temp[tempIdx++] = numbers[i];
      }
    } else { // p에 원소가 남았다.
      for(int i=p; i<=e1; i++) {
        temp[tempIdx++] = numbers[i];
      }
    }
    
    // temp는 완성이 되었으니
    // numbers[s1 ~ e2]까지 temp의 값을 복사
    for(int i=s1; i<=e2; i++) {
      numbers[i] = temp[i-s1];
    } 
    
  }
  
}

 

 

// 코드 : 통과용

import java.util.*;
import java.io.*;
 
public class Main{
  
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
    
    ArrayList<Integer> numbers = new ArrayList<>();
    int n = Integer.parseInt(br.readLine());
    
    for(int i=0; i<n; i++) {
      numbers.add(Integer.parseInt(br.readLine()));
    }
    
    Collections.sort(numbers); 
    
    StringBuilder sb = new StringBuilder();
    for(int i=0; i<n; i++) {
      sb.append(numbers.get(i) + "\n");
    }
    bw.write(sb.toString());
    
    br.close();
    bw.flush();
    bw.close();
  } 
  
}