[BOJ_JAVA] 백준 2751번 : 수 정렬하기2 @달깅

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

 

얘는 대신에 앞에 나온 거와 달리 O(log n)? 뭐 암튼 빅오가 좀 더 작게 나오도록 설계하라는 거였다.

객지프 때 배운 머지 소트 알고리즘을 떠올려서 풀었다!

처음에 mid를 반으로 안 나눠줘서 계속 무한루프 돌ㄹ길래...^^ 너무 화났는데

그거 처리하니까 다 괜찮아 졌다 ㅎㅎ

 

 

---

정답코드

 

 

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

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            int n=Integer.parseInt(br.readLine());
            int[] arr=new int[n];
            for (int i=0; i<n; i++) {
                arr[i]=Integer.parseInt(br.readLine());
            }
            arr=sort(arr);

            for (int i=0; i<n; i++) {
                System.out.println(arr[i]);
            }
        } catch(IOException e) {}
    }

    public static int[] sort(int[] arr) {
        if (arr.length<2) {
            return arr;
        }
        int mid=arr.length/2;
        int[] left=sort(Arrays.copyOfRange(arr, 0, mid));
        int[] right=sort(Arrays.copyOfRange(arr, mid, arr.length));
        arr=merge(left, right);
        return arr;
    }

    public static int[] merge(int[] arr1, int[] arr2) {
        int idx=0;
        int idx1=0;
        int idx2=0;
        int[] result=new int[arr1.length+arr2.length];

        while(idx1<arr1.length && idx2<arr2.length) {
            if (arr1[idx1]<arr2[idx2]) {
                result[idx++]=arr1[idx1++];
            } else {
                result[idx++]=arr2[idx2++];
            }
        }

        while(idx1<arr1.length) {
            result[idx++]=arr1[idx1++];
        }

        while(idx2<arr2.length) {
            result[idx++]=arr2[idx2++];
        }

        return result;

    }
}