수 정렬하기 2(2751)

시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다.

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다.

퀵정렬을 사용해보자?

배열방식을 사용하니까 이게 O(nlogn)은 맞는데 최악의 경우에는 O(n^2)경우가 나와서 에러가 뜬다네...

Array.sort는 dual-pivot Quicksort 알고리즘을 사용

그래서 최악의 경우에 O(nlogn)을 보장하거나 O(n)에 가까운 정렬알고리즘을 찾아서 사용해야하는데 여기서 사용한 방법은 Collectins.sort()을 사용하는 방법임

Collections.sort()는 Timesort 방식이다. 여기서 Timesort방식은 반복 합병 및 삽입정렬알고리즘을 사용하는 방법이고 이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid stable sorting 알고리즘이라고 하는데

합병 알고리즘은 최선 최악 모두 O(nlogn) 을 보장

삽입정렬 알고리즘은 최선은 O(n), 최악은 O(n^2)을 보장

그래서 ArrayList을 사용하고, 진행했는데 또 시간초과가 뜨네? -> 이러면 출력에서 문제가 있을 거임 그래서 StringBuilder을 사용하자

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력

5
5
2
3
4
1

예제 출력

1
2
3
4
5

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i=0; i<N; i++){
            arr.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(arr);


        for(int i=0; i<N; i++){
            sb.append(arr.get(i)+"\n");
        }
        System.out.println(sb);
    }


}

백준