백준 2751번 - 수 정렬하기 2 (Java,병합정렬)

입력이 백만까지 주어지는 문제이기 때문에 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀어야 한다.

병합정렬, 힙정렬, 퀵정렬 등이 있는데

여기서 퀵정렬은 최악의 경우 O(n^2)의 복잡도를 가지기 때문에 퀵정렬로 풀면 오답처리가 된다.

따라서 최악과 평균이 둘다 O(nlogn)인 병합정렬과 힙정렬로 풀 수 있는데

나는 병합정렬로 풀었다.

 

---

 

병합정렬(merge sort)이란?

분할 정복 알고리즘의 하나인 병합정렬은 다음과 같이 작동한다

출처 : https://www.digitalbithub.com/learn/what-is-merge-sort-algorithm

분할 : 먼저 정렬되지 않은 리스트(배열)를 원소가 하나밖에 남지 않을 때까지 절반으로 나눈다.

정복 & 병합 : 나누어진 요소들을 두 개씩 정렬시키면서 합쳐 나간다. 

 

---

병합정렬의 특징?

병합정렬은 분할과정에서 수행 시간이 logN

 

정렬자체에서 수행시간이 N이 필요하므로 시간 복잡도는 O(N logN)이며 이는 평균이나 최악이나 같은 성능을 가진다.

 

일반적으로는 퀵정렬보다 느리지만 성능을 보장한다는 점에서 효율적인 알고리즘이다.

 

그러나 메모리 측면에서 비효율적인데 왜냐하면 정렬과정을 거쳐 병합되기 위해선 기존의 데이터를 담을 추가적인 메모리 공간(배열 등)을 필요로 하기 때문이다.

 

 

---

구현

 

자바로 정답을 맞추기위해선 입출력 버퍼를 써야했다.

스캐너를 쓰니 제한시간 초과가 나왔다.

 

import java.io.*;

public class Main {
    public static int [] tmp; // 정렬에 쓰일 배열 메인 메소드 밖에 선언

    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 size = Integer.parseInt(br.readLine());


        int [] src = new int[size];
        tmp = new int[src.length];

        for(int i=0; i<size; i++){
            src[i] = Integer.parseInt(br.readLine());
        }

        mergeSort(src,0,src.length-1);
        for(int i : src){
            bw.write(i+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static void mergeSort(int[] src, int start, int end){
        if(start < end)  { // start 인덱스와 end인덱스가 같아지는 경우(start가 더 작지 않을 경우)
                           // 나누어진 배열의 요소가 한개 이므로 재귀호출에서 빠져나오도록 if문을 설정
            int mid = (start + end) / 2;
            mergeSort(src, start, mid); // 절반을 기준으로 왼쪽
            mergeSort(src, mid + 1, end); // 절반을 기준으로 오른쪽
            
            //분할이 끝난 후 밑의 정렬을 따른다.
            int p = start;
            int q = mid+1;
            int k = start;
            while(p<=mid && q<=end){
                if(src[p]<=src[q]){
                    tmp[k] = src[p];
                    p++;
                }
                else{
                    tmp[k]=src[q];
                    q++;
                }
                k++;
            }
            if(p>mid){
                for(int i = q; i<=end; i++){
                    tmp[k] = src[i];
                    k++;
                }
            }else{
                for(int i = p; i<=mid; i++){
                    tmp[k] = src[i];
                    k++;
                }
            }
            for(int i = start; i<=end; i++){
                src[i]=tmp[i]; // 정렬된 배열을 원래 배열에 복사
            }
        }
    }
}