Python을 사용한지 1년남짓 되었다.
그중 소팅을 잘 사용중인데, 알고리즘 문제를 풀때에도 잘 사용하는 녀석이다.
문득 알고리즘문제를 풀다가 궁금한게 생겨서 포스팅을 한다.
어떤 문제에서 무심결에 소트를 사용했는데, 우연치 않게 통과가 된것이다.
평범한? c++구현으로는 통과를 못했을텐데...
내용은 뭐냐면 [leetcode] 4. Median of Two Sorted Arrays 문제인데,
만약 Quick sort 였다면, 정렬된 내용을 또 정렬을 하는것이라
시간복잡도가 n2가 되어서 불합격이 되는것인데,
파이썬에서는 TimSort라는 병합정렬을 사용하여 통과를 하였다.
분명 난이도가 Hard인데 체감이 Hard가 아니라서 의심이 들어 좀 찾아보니
이런 내용이다.
참고)
https://medium.com/@fiv3star/python-sorted-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-timsort-dca0ec7a08be
