2751

[Java] 백준 2751: 수 정렬하기 2

일반적인 풀이방법 --> 시간 초과가 발생한다. 아래 더보기를 통해 이유와 코드 확인하기. 더보기 내장 함수를 사용하라고 문제에 나와있지만 Arrays.sort()를 쓰면 시간초과가 발생한다. 이유는 Arrays.sort()는 dual-pivot 퀵 정렬을 사용하기 때문이다. 이 알고리즘은 최악의 경우 시간복잡도가 O(n^2)인 알고리즘이기 때문에 시간초과가 발생할 가능성이 높아지는 것이다. import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] arr = new int[N]; for(int i=0; i