2751번 : 수 정렬하기 2

위 문제에서는 오름차순 정렬을 병합정렬을 통해 정렬한 문제입니다.

N의 최대 범위가 1,000,000 이기 때문에 O(nlogn)의 시간 복잡도로 정렬을 수행하면 됩니다.

병합 정렬 로직
1. 정렬할 그룹을 최소의 길이로 나눕니다.
2. 각 그룹마다 index1과 index2를 지정하여 비교하여 결과 배열에 병합 정렬을 합니다.
3. 정렬 후 하나의 그룹에 요소를 모두 비교한 경우, 나머지 그룹에 남은 요소를 결과 배열에 병합 정렬 합니다.

핵심 로직
재귀 함수 호출을 통해서 그룹을 최소 단위부터 병합정렬할 수 있도록 구현하였습니다.

😀 성공

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

public class Main{
    static int[] arr, tmp;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        
        // 배열에 입력
        arr = new int[N+1];
        tmp = new int[N+1];
        for(int i=1; i <= N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        // 병합정렬
        mergeSort(1,N);
        for(int i =1; i<=N;i++){
            sb.append(arr[i]).append("\n");
        }
        
        // 출력
        br.close();
        System. out.println(sb);
    }
    
    static void mergeSort(int s, int e){
        if(e-s < 1) 
            return;
            
        // 기준값 지정
        int m = s + (e-s)/2;
        
        // 재귀 호출을 통해 최소단위부터 병합정렬
        mergeSort(s,m);
        mergeSort(m+1,e);
        
        for(int i=s; i <= e; i++){
            tmp[i] = arr[i];
        }
        
        int k = s; // 결과 배열의 idx
        int idx1 = s; // pointer 1
        int idx2 = m+1; // pointer 2
        while(idx1 <= m && idx2 <= e){
            if(tmp[idx1] > tmp[idx2]){
                arr[k] = tmp[idx2];
                k++;
                idx2++;
            }else{
                arr[k] = tmp[idx1];
                k++;
                idx1++;
            }
        }
        
        // 병합 정렬 후 남은 요소 결과 배열에 담기
        while(idx1 <= m){
            arr[k] = tmp[idx1];
            k++;
            idx1++;
        }
        
        while(idx2 <= e){
            arr[k] = tmp[idx2];
            k++;
            idx2++;
        }
    }
}