[백준 JAVA] 2751 - 수 정렬하기2

매우 쉬운 문제였지만, 의문이 들었던 문제였다!

 

먼저 시간제한은 2초, 메모리 제한은 256MB라는 점에서, 테스트 케이스가 1,000,000개이기 때문에 그냥 일반 sort를 해도 된다고 생각이 들었다. 

 

그래서 처음에는 Arrays.sort를 했을 때와 Collection.sort의 차이점을 확인해 봤다.

 

[최종코드 - Arrays.sort]

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

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[n];

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

    Arrays.sort(arr);

    for (int num : arr)
        System.out.println(num);
    
    }
}

[최종코드 - Collections.sort]

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

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    ArrayList<Integer> arr = new ArrayList<>();

    for (int i = 0; i < n; i++)
        arr.add(Integer.parseInt(br.readLine()));

    Collections.sort(arr);

    for (int num : arr)
        System.out.println(num);
    }
}

 

위: Collections.sort 아래 Arrays.sort

 

먼저, Arrays.sort()는 dual-pivot Quicksort 알고리즘을 사용하기 때문에 평균 시간 복잡도는 O(nlogn) ~ O(n2)이다.

 

Collections.sort()는 Timsort인데, 이는 합병 및 삽입정렬 알고리즘을 사용한다. 이를 hybrid sorting algorithm라고도 하는데,

이는 시간복잡도 O(n) ~ O(nlogn)을 보장한다는 장점이 있다!

 

그런데,, 위를 보니 Collections.sort()가 더 높게 나왔다.. 이해가 가진 않지만 그래도 해당 sort의 차이를 잘 알게 되었다!

 

배운 점

Arrays.sort()와 Collections.sort()의 차이를 잘 알게 되었다!