[LeetCode][py] 912. Sort an Array

Table of Contents

• 문제
• 예제
• 상황 파악과 계획
• 풀이
  • 1. 제출 오답
    • 코드
    • 반례
    • 오답 사유
  • 2. 참고 풀이
    • 코드
    • 이해

문제

원문 보기: [LeetCode] 912. Sort an Array

정수 배열 nums가 주어졌을 때, 배열을 오름차순으로 정렬하여 반환하라.

내장 함수를 사용하지 않고 O(nlog(n))의 시간 복잡도와 가능한 가장 작은 공간 복잡도로 문제를 풀어야 한다.

조건:

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

예제

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

상황 파악과 계획

문제 파악

정수 배열 제공, 오름차순으로 정렬하여 리턴하라
빌트인 함수 사용 금지, 시간복잡도는 O(nlog(n)), 공간복잡도는 최소로 할 것

계획

1. 선택정렬, 버블정렬은 불가
2. 퀵정렬 가능? 병합정렬은 취향에 안맞아서 못하겠음
3. 퀵정렬을 쓰자. 시간복잡도가 정확히 기억은 안나지만 적어도 로그 단위였던 건 기억함.

여기까지 2분 58초

퀵정렬 참고: 퀵 정렬

풀이

퀵정렬이 유효한 문제인 건 맞는데, 내 코드가 유효하지 않았을 뿐이다.
42분 20초에서 코드 작성을 중단했다. (미련이 남아서 추가 시도한 시간은 안 쟀다)

1. 제출 오답

코드

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) <= 1:
            return nums

        # 피벗은 첫 번째 값
        pivot = 0
        i = 0
        j = len(nums) - 1

        while i < j:
            while nums[i] < nums[pivot]:
                i += 1
            while nums[j] > nums[pivot]:
                j -= 1

            if i <= j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1

        nums[:i] = self.sortArray(nums[:i])
        nums[i:] = self.sortArray(nums[i:])

        return nums

반례

한 쪽을 고치면 다른 한 쪽이 틀렸다.

1. [-1,2,-8,-10]
2. [5,1,1,2,0,0]

오답 사유

내가 알아낸 오답의 과정은 다음과 같다(추측).

1. 피벗을 잡았는데 그게 우연히도 배열 내의 최댓값 또는 최솟값이었다.
2. 배열을 양끝에서 순회해도 피벗을 중심으로 교환할 값의 쌍을 구할 수 없다.
3. 아무것도 교환하지 않은 채로 1번의 순회 및 정렬이 끝나고, 그대로 분할되어 다음 정렬로 넘어간다.
4. 위 과정에서 제대로 정렬되지 않은 값이 계속 부분 배열에 남아 전체적인 정렬을 해친다.

어떻게 하면 최댓값이나 최솟값인 피벗이 제대로 할일을 하게 만들 수 있을지, 또는 최댓값이나 최솟값을 피벗으로 잡지 않을 수 있을지 고민은 해봤는데, 실패했다.

이 글 쓰다가 혹시나 해서 chatGPT에게 질문도 해봤는데 답변과 개선된 코드는 얻었지만 결국 정답 통과는 실패했다. 답안으로서는 의미를 갖지 못했지만 참고를 위해 개선된 코드에서 바뀐 부분만 남기겠다.
피벗을 골랐을 때, 배열 내의 최댓값 또는 최솟값이 아니게 해준다.

# Choose the median of the first, middle, and last elements as the pivot
first = nums[0]
middle = nums[len(nums)//2]
last = nums[-1]
pivot = 0
if first <= middle <= last or last <= middle <= first:
    pivot = len(nums) // 2
elif middle <= first <= last or last <= first <= middle:
    pivot = 0
else:
    pivot = len(nums) - 1

2. 참고 풀이

원본 보기: 7-line quicksort to write in interviews (Python)

Runtime 1314 ms, Beats 63.95%
Memory 23.4 MB, Beats 20.50%

코드

def quicksort(self, nums):
    if len(nums) <= 1:
        return nums

    pivot = random.choice(nums)
    lt = [v for v in nums if v < pivot]
    eq = [v for v in nums if v == pivot]
    gt = [v for v in nums if v > pivot]

    return self.quicksort(lt) + eq + self.quicksort(gt)

이해

퀵정렬의 개념은 그대로 갖고, 파이썬의 특색을 잘 반영한 코드라고 생각한다.

주어진 배열 내에서 자리를 바꾸던 내 코드와 달리, 피벗을 기준으로 값을 솎아내어 새 배열에 나누어 담고 모두 합친 것을 결과로서 반환한다.
다른 언어였다면 배열을 합치는 과정에서 시간을 더 잡아먹거나 훨씬 번거로운 코드가 필요했겠지만 파이썬은 그런 면에서 높은 자유도를 주니까 + 연산자 하나로 끝낼 수 있었다.

다만 런타임과 메모리 면에서 상위권을 차지하지는 못했다.