[leetcode 2024/02/22] 75. Sort Colors

https://leetcode.com/problems/sort-colors/description/

Sort Colors - LeetCode

 

1. 접근 방법

sort()로 풀면 쉽게 풀릴 문제이지만, 친히 ' You must solve this problem without using the library's sort function' 이라고 말씀해 주셨기에, insertion sort [ 삽입 정렬 ] 을 이용해서 풀어볼 것이다.

insertion sort를 이용한 이유는 추가적인 메모리 사용이 거의 없고, nums라는 list에 직접 결과를 반영할 수 있기 때문이다.

 

마침 어제, insertion sort에 대해서 적어둔 것이 있었다.

https://potatoscatteringsmile.tistory.com/138

python의 sort()의 시간 복잡도

 

코드를 작성할 때, 2번 Index 부터 비교하기 시작한 후, 정렬된 부분과 정렬되지 않은 부분으로 나누었다.

이후, 2번 index 부터 시작해서 정렬된 부분의 올바른 위치에 넣어주었다. 

정석적인 insertion sort에 대한 코드는 아래에서 확인하길 바란다.

https://www.geeksforgeeks.org/python-program-for-insertion-sort/

Python Program for Insertion Sort - GeeksforGeeks

 

2. 코드

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

        """
        Do not return anything, modify nums in-place instead.
        """

        for i in range(1, len(nums), 1):
            inserted = False
            compare_n = nums.pop(i)
            for sorted_n in range(0, i, 1):
                if nums[sorted_n] >= compare_n:
                    nums.insert(sorted_n, compare_n)
                    inserted = True
                    break
            if not inserted:
                nums.insert(i, compare_n)

        #print(nums)