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

수 정렬하기2

[2751번: 수 정렬하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net](https://www.acmicpc.net/problem/2751)

---

이 문제는 매우 간단하다 생각하고 풀었는데 시간초과가 뜨면서 틀렸다고 해서 당황했던 문제이다.

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int num = Integer.parseInt(br.readLine());
        int[] m = new int[num]
        for (int i = 0; i <num ; i++) {
            m[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(m);
        for (int i : m) {
            System.out.println(i);
        }
    }
}

처음에 푼 방식이였다. 그냥 Arrays.sort 쓰면 되겠지 했는데 이 방식이 dual-pivot Quicksort 알고리즘을 사용한다.
평균 시간 복잡도가 O(nlogn) 이고 매우 빠른 알고리즘이지만 최악의 경우 시간복잡도는 O(n^2) 이게 된다.

그래서 생각한 방식은 Collections.sort() 를 쓰는 방법이다. Collections.sort()는 Timsort 이다.
Timsort의 경우 합병 및 삽입정렬 알고리즘을 사용한다.
이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid sorting algorithm 이라고 하는데, 합병정렬(Merge Sort)의 경우
최선, 최악 모두 O(nlogn) 을 보장하고, 삽입정렬의 경우 최선의 경우는 O(n), 최악의 경우는 O(n^2) 이다.
그리고 두 정렬 모두 안정 정렬이기 때문에 Timsort를 hybrid stable sorting algorithm 이라고도 한다.
시간복잡도 O(n) ~ O(nlogn)을 보장한다는 장점이 있다. 대신 Collections.sort()를 사용하고자 한다면 가장 쉬운 방법으로 일반적인
primitive 배열이 아닌 List계열(ArrayList, LinkedList등)의 자료구조를 사용하여 정렬해야 한다.

그래서 풀어 본 방식이다.

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int num = Integer.parseInt(br.readLine());

        ArrayList<Integer> list = new ArrayList<>();

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

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

}

이전에는 계속 Scanner를 사용했다. 하지만 BufferReader가 훨씩 속도가 빠르기 때문에 이걸 사용해야겠다.

참고: [https://st-lab.tistory.com/106\](https://st-lab.tistory.com/106)

이 분이 정말 잘 정리해 주셔서 항상 도움이 많이 된다.