[백준] 2751 : 수 정렬하기 (Collections.sort()와 Arrays.sort()) - JAVA

백준 단계별 문제풀이 13단계 (정렬)

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

2751번: 수 정렬하기 2

 

 

# 문제

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

 

# 예제

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

5
5
4
3
2
1

 

출력

1
2
3
4
5

 

# 필요개념

겉보기엔 Arrays.sort로 풀어낼 수 있어 보이지만, 데이터의 개수가 상당히 많아서 시간초과가 일어난다. 일반적으로 연산 1억회를 하는 데 1초정도가 걸린다는 점을 생각하면 100만개의 데이터를 O(n^2)인 알고리즘으로 해결한다면..  상당히 오랜 시간이 걸린다. 참고로 이 문제의 제한시간은 2초이다.

 

Arrays클래스에서 제공하는 sort메소드는 dual pivot Quicksort를 사용한다고 한다. 이 알고리즘의 시간복잡도는 평균 O(nlogn)이나, 우리는 최악의 경우를 따져야 한다. 최악의 경우에는 O(n^2)의 시간복잡도를 가진다는 점에서 시간초과를 야기할 수 있다. 실제로 quicksort를 구현해서 쓰려다가 시간초과로 실패했다.

 

그래서 해당 문제를 풀 떄에는 시간복잡도가 O(nlogn)을 보장하는 알고리즘을 사용해야한다. 그래서 Collections클래스에서 제공하는 sort() 메소드를 사용하였다.

 

 

Collections.sort()

 collections.sort()는 Timsort라는 정렬 알고리즘으로 만들어졌다고 한다. Timsort는 합병 및 삽입정렬 알고리즘을 섞어 사용하는 hybrid sorting algorithm을 사용한다!!

이 알고리즘은 합병정렬의 최악의 경우 + 삽입정렬의 최선의 경우를 조합한 알고리즘이라서 O(n) ~ O(nlogn)의 시간복잡도를 보장한다.

 

그래서 이 메소드를 사용하기 위해 배열이 아닌 리스트에 원소를 담아 사용하였다. 그리고 혹시 몰라서 BufferedReader를 함께 사용해주었다!

 

# Code

import java.io.*;
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());
        List<Integer> list = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(list);

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

 

# 결과