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

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 x : list){
           sb.append(x).append("\n");
       }
        System.out.println(sb);
    }
}

 

 

Arrays.sort를 사용할 경우 primitive type array에 대해 정렬을 할 때, 최악의 상황에서 시간 복잡도가 O(N^2)이기 때문에 시간초과가 난다. 

Collections.sort 의 경우 시간 복잡도가 O(n) ~ O(nlogn)을 보장한다.