목록Collections.sort (1)

리주의 프로그래밍 공부

[11650] 좌표 정렬하기

Arrays.sort는 최악의 경우, 시간 복잡도가 O(n^2)이라 사용하지 않았는데, 다른 사람들의 풀이를 보니, 이 문제에서는 사용해도 됐던 것 같다. (Collections.sort는 Timsort를 사용하여 최악의 경우에도 O(n logn)을 보장한다. insert sort와 merge sort를 섞어쓴다고 한다.) + (Arrays.sort는 형에 따라 쓰는 알고리즘이 달라서 시간복잡도가 다르다고 한다. int형으로 쓴다면, 자바는 Quicksort를 사용해서 최악의 경우 O(n^2)을 가지고, Integer형으로 쓴다면, Mergesort로 O(n logn)을 가진다고 한다. 그렇다면 이 문제에서도 Integer로 쓴다면 걱정없이 Arrays.sort를 쓸 수 있을듯 하다.) 간단한 문제였음에..
알고리즘 공부(백준) 2021. 3. 19. 16:02
이전 Prev 1 Next 다음