[ 백준 ] 2751번 - 수 정렬하기2 / [Java 이용 ]

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int N = sc.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int T = sc.nextInt();
            // 저장 완료
            list.add(T);
        }
        // Arrays 의 sort 로 이용할 경우 시간 복잡도 오류
        //  평균 시간복잡도가 O(nlogn) 이지만 최악의 경우 시간 복잡도 O(n2)
//        Arrays.sort(arr);

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

 

주의해야할 점 :

 

시간 제한이 있기 때문에 이를 Arrays.Sort 로 이용할 경우에는 평소에는 시간복잡도가  O(nlogn)  이지만 최악의 경우 O(n2) 로 쓰이기 되문에 시간 초과가 남. 

- dual-pivot Quicksort 알고리즘을 사용

 

따라서 Collections.sort() 을 이용. 이는 합병 및 삽입 알고리즘을 혼합으로 쓴 hrbrid sorting Algorithm 인데 두 가지의 최선만 짬뽕해서 가져온 알고리즘이다.! 

 

참고

https://st-lab.tistory.com/106 

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