수 정렬하기 2

2751번 : 수 정렬하기2

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 문제이다 java 기준으로 Array.sort메소드를 사용하면 시간초과가 날 가능성이 높음.

Array.sort 의 경우 dual-pivot Quicksort 알고리즘을 사용하기 때문에 최악의 경우 시간복잡도가 O(n^2) 임 ..

이 문제는 Array.sort를 쓰지 않고 풀어야 함 최악의 경우 O(nlogn)을 보장하거나 혹은 O(n)에 가까운 정렬 알고리즘을 사용해야 함

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

public class Sort2 {
    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);
        //list 내의 정수를 오름차순으로 정렬

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

        System.out.println(sb);




    }
}

방법을 찾다가 Collections.sort() 라는 방법이 있다는 것을 알게 됐다. Collections.sort()는 Timesort 방식을 이용한다고 함. Timesort의 경우 합병 및 삽입정렬 알고리즘을 사용하는 것.

1. ArrayList 는 배열과 유사하지만 크기를 동적으로 조절할 수 있음
2. for문을 돌면서 값을 하나 씩 넣어줌.
3. Collections.sort()로 list의 값들을 오름차순으로 정렬
4. sb 객체에는 "1\n2\n3\n4\n5\n"와 같은 문자열이 저장되어 있음.
5. sb 출력.