[LeetCode] 912. Sort an Array

- Problem

912. Sort an Array

빌트인된 함수를 사용하지 않고 정수 배열 nums를 오름차순으로 정렬해야 하는 문제이다.

문제의 제약 조건은

• 시간 복잡도 O(NlogN)을 만족하고,
• 최대한 메모리 공간을 효율적으로 사용하는 알고리즘으로 푸는 것이다.

worst case가 주어졌을 때도 O(NlogN)의 시간 복잡도를 만족하는 알고리즘으로는, Merge Sort, Quick Sort, Heap Sort... 등이 있다.

- 내 풀이 (Counting Sort)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        MIN_VAL, MAX_VAL = -50000, 50000
        num_freq = defaultdict(int)

        for num in nums:
            num_freq[num] += 1
        
        sorted_nums = []
        
        for i in range(MIN_VAL, MAX_VAL+1):
            if i in num_freq:
                sorted_nums.extend([i]*num_freq[i])
        
        return sorted_nums

- 결과

• 시간 복잡도: O(N+K) (N은 배열의 길이, K는 nums[i]의 range)
• 공간 복잡도: O(K)

결론적으로는, 문제의 제약 조건을 만족하지 않는 알고리즘이다.

임의의 정수 nums[i]의 값이 광범위하게 커진다면, 부분적으로 O(NlogN)의 시간 복잡도를 가지는 알고리즘보다 느리게 동작할 수 있는 알고리즘이다.
즉, 카운팅 소트는 기본적으로 O(N)의 시간 복잡도를 만족하지만, 상수항의 최댓값에 따라 훨씬 비효율적일 수도 있다. 메모리 공간 또한 마찬가지이다.

"더 나은 시간 복잡도를 가진다고 해서 더 빠른 효율을 자랑할 수 있을까?"에 대한 의문을 가지고 있었는데, 이러한 방법으로 문제를 접근하니 조금은 해답을 얻은 듯 하다.