단순한 정렬문제이다.
import sys
input = sys.stdin.readline
N = list(input().rstrip())
N.sort(reverse=True)
print("".join(N))python에서 list를 정렬할 때 기본적으로 내장된 sort()함수를 사용해도 시간 초과엔 문제가 되지 않는다. 오히려 흔히 배우는 quickSort, mergeSort 등을 직접 구현해서 돌릴 경우 시간이 훨씬 오래 걸리는 것을 확인할 수 있다.
python 내장함수 sort는 어떤 알고리즘을 이용하는 걸까?🤔
결론부터 말하자면, TimSort 알고리즘을 사용한다.
TimSort?
2002년 소프트웨어 엔지니어 Tim Peters에 의하여 만들어진 알고리즘으로, InserSort와 MergeSort를 결합하여 만든 Hybrid 정렬 알고리즘이다.
TimSort는 미리 어느 정도 정렬된 부분이 존재하는 실생활 데이터의 특성을 고려해 더 빠르게 작동하도록 고안되었다. 완전히 무작위인 데이터에 대해서는 속도가 빠른 편은 아니지만 일정한 패턴이 있는 일반적인 데이터에 대해서는 빠른 성능을 보여준다.
InserSort와 MergeSort라는 안정적인 두 정렬방법을 결합했기 때문에 TimSort 또한 안정적이고, 추가메모리를 사용하긴 하지만 Mergesort에 비해 적은 추가 메모리를 사용한다.
안정적(Stable)인 정렬 알고리즘 : 같은 값들끼리 위치가 그대로 유지됨
최선의 경우 시간복잡도는 O(n), 평균 및 최악의 경우 O(nlogn)의 시간복잡도를 가진다.
TimSort의 자세한 동작 방법이 궁금하다면 첨부된 링크에 들어가서 확인하도록 하자.
