백준 BOJ 2751번 - 수 정렬하기 2

---

접근 방법

 

Arrays.sort() 로 풀면 시간초과가 나는 문제다. Arrays.sort() 는 평균이 O(nlogn)이지만 최악의 경우 O(n^2)이다.

이를 해결하기 위해서 Collections.sort() 를 사용해야 한다.

Collections.sort() 는 ArrayList를 사용하여 Tim Sort 방식으로 정렬한다. 시간복잡도는 O(n) ~ O(nlogn)

 

 

 

+ 시간이 문제다 싶으면 StringBuilder를 사용해보자

---

코드

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            arr.add(in.nextInt());
        }
        Collections.sort(arr);
        for(int i = 0; i < n; i++){
            sb.append(arr.get(i)).append("\n");
        }
        System.out.println(sb);
    }
}