[백준] 2751번 수 정렬하기 2 자바(Java)

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

---

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();

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

        Collections.sort(list);

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

설명

처음에 Arrays.sort()를 사용해 풀었지만 시간초과가 발생해 실패했다.
Arrays.sort()의 경우 평균 시간복잡도가 O(nlogn)이고 매우 빠른 알고리즘이지만, 최악의 경우 시간복잡도는 O(n^2)이다.
따라서, Collections.sort()를 사용해 문제를 풀었다.

그럼 Arrays.sort()로는 풀 방법이 없을까? 결론부터 말하자면 풀 수 있다.
참고
Arrays.sort()는 worst case의 속도가 Arrays.sort(int) < Arrays.sort(Integer)이다.
데이터 타입이 primitive 일 때 Arrays.sort는 Quick sort를 사용하지만,
Integer와 같은 객체일 때는 Merge sort를 사용하기 때문이다.
worst case일 때, Quick sort는 시간복잡도는 O(n^2)이지만, Merge sort는 시간복잡도가 O(nlogn)이기 때문에
Arrays.sort(Integer)를 사용해서 풀 수도 있다.

Arrays.sort() 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        Integer[] arr = new Integer[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        for (int i = 0; i < N; i++) {
            sb.append(arr[i]).append('\n');
        }
        System.out.println(sb);
   }
}