백준 문제 풀이 2751 | JAVA

2751번: 수 정렬하기 2 (acmicpc.net)

 

2750번으로 풀면 시간 초과가 난다.

= Collections.sort() 이용 : Timsort = 합병+삽입 정렬 알고리즘을 사용

합병 정렬의 최선 = O(n log n), 최악 = O(n log n)

삽입 정렬의 최선 = O(n) , 최악 = O(n^2)

Timsort의 시간복잡도는 O(n) ~ O(nlogn) 

 

StringBuilder를 사용해 한 번에 출력해야 시간 초과가 나지 않음 

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

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());
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(list);

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