[백준 (Baekjoon)] (java) 문제 2751

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

2751번: 수 정렬하기 2

1) 접근법

정말 빠르게 풀지 않으면 시간초과가 나버리는 문제였다.
그래서 처음에는 퀵 소트로 풀어볼까 하였으나 퀵 소트의 가장 취약점인 반대로 정렬되어있는 반례가 있는 듯 하였다. 퀵 소트는 평균적으로는 O(NlogN) 속도를 보이나 최악의 경우에서는 O(N^2)의 속도를 보여 시간초과 문제가 발생했다.
따라서 조금 더 stable한 시간복잡도를 보이는 merge sort로 구현하였다.

 

2) 시간 복잡도

O(NlogN)

 

3) 이 문제로 얻은 것 + 소감

- Merge sort 구현법

- 이 전까지는 merge sort에 대해 크게 생각해본 적도 없었고 심지어 그저 quick sort의 하위호환이라고 생각하기도 했으나 이번 문제를 풀며 merge sort의 안정적인 시간복잡도에 대해 생각해보게 되었다

 

4) 코드

import java.io.*;

public class p2751 {
    static BufferedReader br;
    static BufferedWriter bw;

    static int[] list;
    static int N;

    public static void main(String[] args) throws IOException{
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        list = new int[N];

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

        mergeSort(0, list.length-1);

        StringBuilder sb = new StringBuilder();
        for(int num:list){
            sb.append(num+"\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private static void mergeSort(int start, int end){
        if(start<end){
            int mid = (start+end)/2;
            mergeSort(start,mid);
            mergeSort(mid+1,end);
            merge(start, mid, end);
        }
    }

    private static void merge(int start, int mid, int end){
        int temp[] = new int[end-start+1];
        int l=start, r=mid+1, idx = 0;

        while(r<=end && l<=mid){
            if(list[l]<=list[r]) temp[idx++] = list[l++];
            else temp[idx++] = list[r++];
        }

        while(r<=end) temp[idx++] = list[r++];
        while(l<=mid) temp[idx++] = list[l++];

        for(int i=0;i<temp.length;i++){
            list[i+start]=temp[i];
        }

    }
}