백준 2750번 수 정렬

미리 재귀 깊이 더 늘려놓기

import sys
sys.setrecursionlimit(10000)

class Sort:
    def read(self):
        self.n = int(input())
        self.item=[]
        for _ in range(self.n):
                self.item.append(int(input()))

    def answer(self):
        self.item=self.Quicksort(self.item)
        for item in self.item:
            print(item,end='\n')

시간복잡도 : O(nlogn)

from IPython.display import Image
Image(filename='/Users/baekjiyoon/Desktop/sortingtime.jpeg')

output_5_0

    def Quicksort(self,array):
        if len(array)<2:
            return array
        else:
            pivot=array[0]
            less=[i for i in array[1:] if i<=pivot]
            greater=[i for i in array[1:] if i>pivot]          #lesser,greater 둘 다 실행하면 O(n)

            return self.Quicksort(less)+[pivot]+self.Quicksort(greater)  #운이 좋은 경우 O(n) 이 logn 번만 반복 

메모리와 시간 제한만 다른 동일 문제 2751번은 퀵소트 똑같이 적용하니까 시간 초과가 떴다. 아직 정렬 알고리즘 제대로 이해하는 것은 퀵소트밖에 없는데 딴 거 더 배운 다음에 다른 걸로 적용해봐야겠다.