[리트코드/leetcode/python] 912. Sort an Array

이미지를 누르면 문제 링크를 보실 수 있습니다

 

오늘은 머지소트와 관련한 문제를 가져와봤습니다. 해당 문제는 Medium 난이도이지만, 어떠한 내장함수도 사용하지 않고, O(nlogn) 시간복잡도로 풀어야 하는 것이 관건입니다. 

문제 설명

리트코드 912번 Sort an Array 문제는 주어진 정수 배열을 오름차순으로 정렬하는 알고리즘을 구현하는 것입니다. 배열에는 중복된 값이 포함될 수 있으며, 출력 시 동일한 값의 순서는 그대로 유지되어야 합니다. 이는 기본적인 정렬 알고리즘을 연습하는 데 중요한 문제로, 다양한 정렬 기법을 활용할 수 있습니다. 다시 한번 강조하지만, 어떠한 내장함수도 사용하면 안됩니다. 즉, 이 문제는 정렬 함수를 쓰지 않고 직접 정렬 알고리즘을 구현할 수 있는지의 능력을 판단하려고 하는 것 같습니다. O(nlogn) 시간으로 말이죠.

문제 해결 과정

1. 초기 접근 : 문제 이해하기

 

우선 문제를 이해하고 어떤 정렬 알고리즘이 적합할지 고려했습니다. 대표적인 정렬 알고리즘으로는 합병 정렬(Merge Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 계수 정렬(Counting Sort), 기수 정렬(Radix Sort) 등이 있는데요, 각 정렬의 특징은 다음과 같습니다.

 

퀵 정렬(Quick Sort)

분할정복(divide-conquer) 방법을 사용하여 배열을 정렬합니다. 피벗을 선택하고, 이를 기준으로 작은 값과 큰 값을 나눕니다. 평균 시간복잡도는 O(nlogn) 성능을 보이지만,  최악의 경우 O(n^2)의 시간복잡도를 가집니다. 공간 효율성이 뛰어납니다.

 

퀵 소트의 동작 방식을 보고 싶다면, 아래 유튜브 영상을 참고하세요.

https://www.youtube.com/watch?v=Vtckgz38QHs

 

 

병합 정렬(Merge Sort)

배열을 작은 단위로 분할한 후 다시 병합하여 정렬합니다. 모든 경우에 O(nlogn)의 시간복잡도를 가지며, 안정적인 정렬을 제공합니다. 메모리 사용량이 크지만, 대규모 데이터 세트에 적합합니다.

 

병합 정렬의 동작 방식을 보고 싶다면, 아래 유튜브 영상을 참고하세요.

https://www.youtube.com/watch?v=3j0SWDX4AtU

 

 

힙 정렬(Heap Sort)

최대 힙 또는 최소 힙을 이용하여 정렬하는 알고리즘입니다. 힙은 완전 이진트리 형태로, 부모 노드가 자식 노드보다 크거나 작은 성질을 가집니다. 모든 경우에 O(nlogn) 시간복잡도를 유지하며, 공간 복잡도는 비교적 낮습니다. 그러나 불안정한 정렬입니다.

 

힙 정렬의 동작 방식을 보고 싶다면, 아래 유튜브 영상을 참고하세요.

https://www.youtube.com/watch?v=2DmK_H7IdTo

 

계수 정렬(Counting Sort)

요소의 빈도를 계산하여 정렬합니다. 시간복잡도는 O(n+k)로 매우 효율적이나, 메모리 사용이 크기 때문에, 요소의 범위가 제한된 경우에 유리합니다.

 

계수 정렬의 동작 방식을 보고 싶다면, 아래 유튜브 영상을 참고하세요.

https://www.youtube.com/watch?v=7zuGmKfUt7s

 

 

기수 정렬(Radix Sort)

기수 정렬은 숫자를 자릿수별로 나누어 정렬하는 알고리즘입니다. 각 자리의 값을 기준으로 여러 번 정렬하며, 작은 자릿수부터 큰 자릿수 순으로 처리합니다. 이를 위해 계수 정렬(Counting Sort)와 같은 안정적 정렬 알고리즘을 사용합니다. 시간복잡도 O(d * (n+k)) 에서, d는 자릿수, n은 요소 수, k는 기수이고 공간복잡도는 O(n+k)입니다. 데이터의 자릿수가 작은 경우 매우 효율적이지만, 데이터의 자릿수가 크거나 기수가 크면 메모리 사용량이 증가합니다.

 

기수 정렬의 동작 방식을 보고 싶다면, 아래 유튜브 영상을 참고하세요.

https://www.youtube.com/watch?v=nu4gDuFabIM

 

 

처음에는 퀵소트로 빨리 풀어서 통과가 됐지만, 두 달 후에, TLE(시간초과)가 발생했다는 한 유저

 

리트코드 자체에서 문제를 개선했다고 합니다ㅋㅋ

 

어떤 유저가 JS로 각 정렬에 대해 통과여부를 정리했습니다. 언어마다의 차이는 있겠죠.

 

Discussion에서 마지막 유저가 말한 바에 따르면, Radix sort가 가장 빠르고, 그 다음 Heap sort, Merge sort 순인 것 같습니다. 개인의 선호도에 따라서 어떤 정렬을 쓸 것인가를 정하면 될 것 같습니다.

 

저는 안정성이 좋고 일관된 성능(O(nlogn))을 가지는 머지소트를 사용하여 이 문제를 해결했습니다. 큰 데이터 세트를 처리할 때도 유리하고, 머지소트를 잘 구현할 줄 알면 웬만한 문제에서는 적용가능할 수 있기 때문입니다. 

 

머지소트에서는 배열의 중간 인덱스를 기준으로 분할하여 작은 문제로 나눕니다. divide conquer(분할 정복) 전략을 사용해서 재귀적으로 정렬하여 부분 배열을 정렬하고, 정렬된 부분 배열을 다시 병합하며 최종 정렬된 배열을 만들면 됩니다.

---

 

2. 병합 정렬(머지 소트)을 이용한 해결 방법

 

먼저, 'merge_sort' 함수 입니다.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
    
        def merge_sort(arr,l,r):

            if l == r:
                return arr
            
            mid = (l+r) // 2
            merge_sort(arr,l,mid)
            merge_sort(arr,mid+1,r)
            merge(arr,l,mid,r)
            return arr
        
        return merge_sort(nums,0,len(nums)-1)

 

'merge_sort' 함수는 배열을 재귀적으로 분할하고, 분할된 부분 배열을 정렬한 후 병합합니다.

 

- 분할 기준: 'mid'는 배열을 반으로 나누는 인덱스입니다.

- 재귀 호출 : 배열을 'l'에서 'mid'까지, 그리고 'mid+1'에서 'r'까지 분할하고 각각 정렬합니다.

- 병합 : 정렬된 두 부분 배열을 'merge' 함수를 사용하고 병합합니다.

 

그럼, 'merge' 함수를 살펴봅시다.

def merge(arr,L,M,R):

            left,right = arr[L:M+1], arr[M+1:R+1]

            i = L
            j,k = 0, 0

            while j < len(left) and k < len(right):

                if left[j] <= right[k]:
                    arr[i] = left[j]
                    j += 1
                else:
                    arr[i] = right[k]
                    k += 1
                i += 1
            
            while j < len(left):
                nums[i] = left[j]
                j += 1
                i += 1
            while k < len(right):
                nums[i] = right[k]
                k += 1
                i += 1

 

이 함수는 두 개의 정렬된 부분 배열을 병합하여 하나의 정렬된 배열을 만듭니다. 여기서 'L', 'M', 'R' 은 각각 배열의 왼쪽, 중간, 오른쪽 인덱스를 나타냅니다.

왼쪽 배열('left') 는 'arr[L:M+1]' (배열의 첫 번째 부분)

오른쪽 배열('right') 는 'arr[M+1:R+1]' (배열의 두 번째 부분)

 

함수는 두 배열을 순회하면서 작은 요소를 결과 배열에 넣고, 남은 요소들은 순서대로 추가합니다.

 

- 초기화 : 'i'는 병합된 배열의 인덱스, 'j' 와 'k' 는 각각 왼쪽과 오른쪽 배열의 인덱스를 나타냅니다.

- 비교 및 병합 : 두 배열을 비교하여 작은 요소를 병합된 배열에 추가하고 인덱스를 증가시킵니다.

- 잔여 요소 추가 : 한 배열의 요소를 모두 사용한 후 남은 다른 배열의 요소들을 병합된 배열에 추가합니다.

 

---

 

3. 최종 코드 및 결과

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:

        def merge(arr,L,M,R):

            left,right = arr[L:M+1], arr[M+1:R+1]

            i = L
            j,k = 0, 0

            while j < len(left) and k < len(right):

                if left[j] <= right[k]:
                    arr[i] = left[j]
                    j += 1
                else:
                    arr[i] = right[k]
                    k += 1
                i += 1
            
            while j < len(left):
                nums[i] = left[j]
                j += 1
                i += 1
            while k < len(right):
                nums[i] = right[k]
                k += 1
                i += 1

            
        def merge_sort(arr,l,r):

            if l == r:
                return arr
            
            mid = (l+r) // 2
            merge_sort(arr,l,mid)
            merge_sort(arr,mid+1,r)
            merge(arr,l,mid,r)
            return arr
        
        return merge_sort(nums,0,len(nums)-1)

시간복잡도

Lessons Learned

이상으로 912. Sort an Array 문제에 대해 정리해봤습니다. 이 문제를 통해 정렬 알고리즘을 이해하고 직접 구현하는 것이 알고리즘 문제 해결의 기초를 다지는 데 매우 중요한 것을 배웠습니다. 머지소트를 비롯한 각각의 정렬 특징을 파악하고 내장함수를 사용하지 않고 직접 구현하는 힘을 훈련하도록 합시다.

---