[알고리즘][백준][JAVA] 2751번 : 수 정렬하기 2

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

2751번: 수 정렬하기 2

먼저, 해당 문제는 N개의 수를 입력받은 뒤 오름차순으로 정렬하는 문제인데, 

일반적인 정렬 방법인 Arrays.sort() 를 사용하면 시간 초과가 난다.

- Arrays.sort() 는 dual-pivot QuickSort 알고리즘을 사용하는데, 이는 평균 시간복잡도는 O(n logn) 이지만 worst의 경우는 O(n^2) 이기 때문에 런타임 에러가 날 수 있기 때문이다.

 

해결 방법으로는 Collections.sort() 가 있는데, 이는 TimSort 라는 알고리즘을 사용하며 합병 및 삽입정렬을 사용한다.

TimSort 의 경우 O(n) ~ O(n logn) 의 시간복잡도를 가지기 때문에 효율적이다.

 

하지만 Collections.sort() 를 이용하려면 일반적인 primitive 배열이 아닌, ArrayList / Linked List 등 List 계열의 구조를 꼭 이용하여야 한다.

 

 

(++출력에 추가한 코드)

System.out.println() 을 이용해 결과값을 출력하는 방법보다, StringBuilder 를 이용하여 출력하면 훨씬 빠르게 출력할 수 있다.

StringBuilder는 새로운 객체를 생성하여 String 과 문자열을 더하는 것이 아닌, 기존의 데이터에 더하는 방식을 사용하기 때문이다.

 

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        StringBuilder sb=new StringBuilder();
        ArrayList<Integer> list = new ArrayList<>();

        int N = sc.nextInt();
        for (int i=0;i<N;i++){
            list.add(sc.nextInt());
        }

        Collections.sort(list);     // Collections.sort()는 Tim Sort 를 수행한다. ( O(n) ~ O(nlogn) )

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

        System.out.println(sb);     // 츨력으로 StringBuilder를 사용하면, 속도도 빠르고 부하가 적다.
    }
}