백준 2751번 수 정렬하기2

1. 문제 설명

문제 링크

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

입력

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

.

출력

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

2. 코드

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.io.IOException;

import java.util.ArrayList;

import java.util.Collections;

 

class Main {

    public static void main(String[] args) throws IOException {

        // Scanner 보다 빠른 입력을 위한 입력 객체 할당

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

 

        // StringBuilder 객체 할당

        StringBuilder sb = new StringBuilder();

 

        // n 값 입력

        int n = Integer.parseInt(br.readLine());

 

        // 숫자를 넣고 정렬 위한 리스트 할당

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

 

        // n값 만큼 반복문을 돌려서 ans 리스트에 정렬 할 숫자값 넣기

        for (int i = 0; i < n; i++) ans.add(Integer.parseInt(br.readLine()));

 

        // Timsort

        Collections.sort(ans);

 

        // ans안의 요소를 num으로 할당하여 StringBuilder에 값넣기

        for (int num: ans) sb.append(num).append("\n");

 

        // 출력

        System.out.println(sb);

    }

}

3. 회고

Q. 문제를 보고 든 생각

• • 일반적인  Arrays.sort() 사용 하면 풀릴 줄 알았던 문제이다.
  • 하지만 시간초과를 받았고 Arrays.sort()의 시간복잡도에 대해 검색하여 알게된 결과Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 사용한다고 했다. 물론 평균 시간복잡도가 O(nlogn) 이고 매우 빠른 알고리즘인 것은 맞다. 그러나 최악의 경우 시간복잡도는 O(n2) 이라는 점을 기억해야한다.
  • 해결방법은??
  • 첫 번째는 Collections.sort() 를 쓰는 방법이다. Collections.sort() 은 Timsort이다. Timsort 의 경우 합병 및 삽입정렬 알고리즘을 사용한다.
  • 이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid sorting algorithm 이라고 하는데, 합병정렬(Merge Sort)의 경우 최선, 최악 모두 O(nlogn)  을 보장하고. 삽입정렬(Insertion sort)의 경우 최선의 경우는 O(n) , 최악의 경우는 O(n2) 이다. 그리고 두 정렬 모두 안정 정렬(stable sort)이기 때문에 Timsort를 hybrid stable sorting algorithm이라고도 한다.
  • 즉, 합병정렬의 최악의 경우와 삽입정렬의 최선의 경우를 짬뽕한 알고리즘이 Timsort 라는 것이다. 실제로 파이썬이나 기타 정렬 알고리즘에서 가장 많이 쓰이는 알고리즘이기도 하다.
  • 시간복잡도 O(n) ~ O(nlogn) 을 보장한다는 장점이 있다. 대신에 Collections.sort()를 사용하고자 한다면 가장 쉬운 방법으로는 일반적인 primitive 배열이 아닌 List 계열(ArrayList, LinkedList 등..)의 자료구조를 사용하여 정렬해야한다.

4. 고쳐야 할점

더 좋은방식이 있다면 알려주세요