백준 - 2751번 - 수 정렬하기 2

2751번

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int num = Integer.parseInt(bf.readLine());
		ArrayList<Integer> list = new ArrayList<>();

		for (int i = 0; i<num; i++) {
			list.add(Integer.parseInt(bf.readLine()));
		}

		Collections.sort(list);

		for (int N : list) {
			sb.append(N).append('\n');
		}
		System.out.println(sb);
	}

}

풀이

---

일반적인 Arrays.sort(list); 를 사용하는 방법이 대표적이다. 이 방법은 dual-pivot Quicksort 알고리즘을 사용하는 것으로 알고 있는데 평균적으로 시간복잡도가 O(nlogn)을 갖지만 최악의 경우에는 O(n2)까지 잡아먹는다.

그래서 다른 방법으로 풀어야하는데 Collections.sort(list); 사용하였다. Collections.sort는 Timsort이다. Timsort 의 경우 합병 및 삽입정렬 알고리즘을 사용한다.

이것은 시간복잡도 O(n) ~ O(nlogn) 을 보장한다는 장점이 있다. 대신에 Collections.sort()를 사용하고자 한다면 가장 쉬운 방법으로는 일반적인 primitive 배열이 아닌 List 계열(ArrayList, LinkedList 등..)의 자료구조를 사용하여 정렬해야한다.