Sort Colors

문제 번호, 이름: 75. Sort Colors

문제 링크: https://leetcode.com/problems/sort-colors/description

날짜: 2024/06/12

상태: 완료

 

이 문제를 고른 이유

리트코드 오늘의문제

문제 보고 처음 든 생각

5년 전에 제출한 풀이가 있었다. 보진 않았다

constance space를 써서 소트를 해라? 근데 n <= 300이다? 그냥 버블소트 하면 되는 거 아닌가.. 물론 더 빨리 풀려면 constance space를 쓰는 NlogN 소트같은걸 떠올려봐도 될 것 같다.

 

풀이 v1

• 소요 시간 3분

버블소트!

 

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(n-1):
            for j in range(i+1, n):
                if nums[i] <= nums[j]:
                    continue
                else:
                    tmp = nums[i]
                    nums[i] = nums[j]
                    nums[j] = tmp

 

속도는 상위 27% 메모리는 상위 3%

다들 그냥 버블소트로 했나보다. 아니면 n이 너무 작아서 상관없었거나

추가로 쓴 메모리는 n, i, j, tmp 니까 상수 공간 맞다 

풀이 v2

• 소요 시간 -

# v2 없음

 

 

이 문제를 풀고 얻은 것

•  

메모

• 너무 금방 풀었는데..?
• 그 뭐냐 버킷소트? array elem이 3종류로 제한되어있으니까 이걸 의도하고 낸 것 같기도..