[Java] 백준 2751: 수 정렬하기 2

일반적인 풀이방법 --> 시간 초과가 발생한다.

아래 더보기를 통해 이유와 코드 확인하기.

내장 함수를 사용하라고 문제에 나와있지만

Arrays.sort()를 쓰면 시간초과가 발생한다.

 

이유는 Arrays.sort()는 dual-pivot 퀵 정렬을 사용하기 때문이다.

이 알고리즘은 최악의 경우 시간복잡도가 O(n^2)인 알고리즘이기 때문에 시간초과가 발생할 가능성이

높아지는 것이다.

import java.util.*;

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

        int N = sc.nextInt();
        int[] arr = new int[N];

        for(int i=0; i<N ; i++){
            arr[i]=sc.nextInt();
        }
        
        Arrays.sort(arr);

        for(int i=0; i<N ; i++){
            System.out.println(arr[i]);
        }
    }
}

시간 초과를 방지하기 위해 

TimeSort (합병 및 삽입정렬) 알고리즘을 사용하는 Collenctions.sort()를 사용할 것이다.

 

위 알고리즘은 O(n) ~ O(nlogn)의 시간복잡도를 보장하는 강력한 정렬 알고리즘이다.

 

위 함수를 사용할 때 주의할 점은 일반적인 배열을 사용하면 안되고

ArrayList나 LinkedList와 같은 자료구조를 사용해야 동작한다.

 

 

 

Scanner로 그냥 받아서 사용할 때도 시간초과가 나므로

StringBuilder를 이용해서 문제를 해결하였다.

 

import java.util.*;

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++){
            list.add(sc.nextInt());
        }

        Collections.sort(list);

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