[백준] 수 정렬하기 2_ JAVA

o 문제

 

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

 

---

 

 

o 풀이

 

시간 복잡도가 중요한 문제라 기본 배열로 Arrays.sort() 를 쓰면 무조건 시간초과가 난다!

그래서 List를 생성해서 Collections.sort()

 

 

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int tc = in.nextInt();

        List<Integer> list = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

        for (int TC = 0; TC < tc; TC++) {
            list.add(in.nextInt());
        }
        Collections.sort(list);
        for(Integer i : list){
            sb.append(i).append('\n');
        }
    }
}

 

 

그리고 아래와 같이 배열 반복문에서 바로 출력하는 코드를 쓰는 것은 출력 작업에 많은 시간을 쓰게 되니

위 코드 처럼 StringBuilder를 사용하여 값을 누적하고 한번만 출력하는 것이 시간이 줄어든다.

        Collections.sort(list);
        for(Integer i : list){
            System.out.println(i);
        }

 

 

Arrays.sort()는 primitive arrays에 대해 Dual-Pivot Quicksort 을 수행한다.
평균 시간복잡도가 O(nlogn)이지만 최악의 경우 시간복잡도는 O(n^2)

 

Collections.sort()은 Object type arrays에 대해 Merge Sort 보다 향상된 Tim Sort 를 수행한다.
Tim sort란 합병정렬의 최악의 경우와 삽입정렬의 최선의 경우를 짬뽕한 알고리즘으로 시간복잡도는 O(n) ~ O(nlogn) 을 보장한다,