[LeetCode] 912번 Sort an Array 문제를 풀어보았다. (ft. java)

2023년 03월 01일 수요일 - 대황T1!

오늘 올려볼 문제는 912번 Sort an Array 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

오랜만에 sort 구현해봤네 ㅎㅎ

입력

사진에서도 볼 수 있듯이 int 배열 1개가 입력으로 들어온다.

---

풀이 및 코드

시간 복잡도 nlogn 인 정렬을 직접 구현하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

머지소트로 진행했다~

이제 코드를 봐보자!

풀이코드

class Solution {
    int[] arr;
    public int[] sortArray(int[] nums) {
        arr = nums;
        sort(0, nums.length - 1);
        return arr;
    }
    
    public void sort(int left, int right) {
        int mid = left + (right - left) / 2;
        if(right - left > 1) {
            sort(left, mid);
            sort(mid + 1, right);
            merge(left, mid, mid + 1, right);
        } else {
            if(arr[left] > arr[right]) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
    }
    
    public void merge(int ls, int le, int rs, int re) {
        var tArr = new int[re - ls + 1];
        int li = ls, ri = rs;
        
        for(int i = 0; i < tArr.length; i++) {
            if(li <= le && ri <= re) 
                tArr[i] = arr[arr[li] < arr[ri] ? li++ : ri++];
            else if(li > ls && ri <= re) 
                tArr[i] = arr[ri++];
            else 
                tArr[i] = arr[li++];
        }
        
        for(int i = 0; i < tArr.length; i++) arr[ls + i] = tArr[i];
    }
}

---

제출 화면

뭔가 오랜만에 이런 구현을 직접해서 그런지 예쁘게 구현하지는 못한것 같다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.