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

---

2751번 수 정렬하기 2번문제인데 앞의 문제인 2750문제보다 수의 범위가 훨씬 넓어졌다.

 

따라서 코드에 대해 좀 더 정교한 필요하다.

 

예를 들어 2750번에서는 가능했어 Arrays.sort를 사용하면 시간초과가 발생한다.

 

여기서 약간의 정리를 하자면

Arrays.sort()의 경우에는 dual-pivot quicksort 알고리즘을 사용한다. quciksort가 평균 시간복잡도 o(nlogn)으로 좋은 알고리즘이긴 하지만 최악의 경우에는 o(n^2)이라는 것을 알아야한다.

 

또한 이 문제에서는 일부러 최악의 경우를 배치시켜 시간초과 문제가 발생하도록 했다.

 

위의 문제를 해결하기 위해서는 Collections.sort()라는알고리즘을 사용해야 한다. 이 알고리즘은 반복합병 및 삽입 알고리즘을 사용하는데 시간복잡도 o(n) ~ o(nlogn)을 보장한다.

 

따라서 Arrays.sort() 대신 Collection.sort()를 사용해야한다.

 

그리고 또 한가지 주의해야 할 점이 있다.

바로 프린트를 해줄때 배열의 원소를 하나씩  출력하면 시간 초과가 발생한다는 것이다.

즉 StringBuider를 사용해서 한번에 출력해줘야 한다.

 

코드

package baekjoon;

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

public class num_sort2 {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int n = in.nextInt();

        ArrayList<Integer> list= new ArrayList<>();

        for(int i = 0; i<n;i++){
            list.add(in.nextInt());
        }
        Collections.sort(list);

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