[알고리즘] 백준 - 2751 (수 정렬하기 2) / 자바

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
 
public class Main {	
	public static void main(String[] args) {   
		Scanner in = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int N = in.nextInt();
		ArrayList<Integer> list = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			list.add(in.nextInt());
		}
		
		Collections.sort(list);
		
		for(int value : list) {
			sb.append(value).append('\n');
		}
		System.out.println(sb);
	}
}

처음에 Quick Sort로 접근했다가 시간초과가 났다. 찾아보니 Array에서 기본적으로 제공하는 sort() 메서드도 퀵 소트를 사용한다고 한다. 정답률이 30%인데 이러한 메서드로 통과될 리도 없고 모르겠어서 인터넷을 찾아봤더니 Collections.sort() 를 사용하면 된다고 한다. Collections.sort()는 Merge sort와 Insert sort을 짬뽕한 알고리즘을 사용한다. Merge sort는 최선 최악 모두 $O(NlogN)$ 을 보장하고 Insert sort는 최선의 경우 $O(N)$ , 최악의 경우 `$O(N^2)$ 이다. 이들의 최선의 경우를 적절한 짬뽕한 알고리즘을 사용한다고 하니까 유용하게 사용할 수 있을 것이다.