Java 백준 2751번 문제 - 수 정렬하기2

수 정렬하기 2 성공

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

151169

40963

27924

29.985%

문제

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

입력

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

출력

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

예제 입력 1 

5
5
4
3
2
1

예제 출력 1 

1
2
3
4
5

---

2750번 문제인 수 정렬하기 문제와 많이 비슷한데,

차이점이라면 데이터도 이전 문제에 비해 1000배 많아졌고, 수의 범위도 1000배 넓다.

 

이 전 문제에서 Arrays.sort를 사용하면 시간 초과가 발생해서 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라는 것이다.

 

하지만 Collections.sort만 써서는 시간초과가 또 발생해서

기존에 System.out.println으로 출력했던 방식에서

StringBuilder를 사용하는 방식으로 바꾸었더니 문제를 성공하였다 

 

코드에 대한 풀이 방법은 이전 2750번 문제를 참고하면 된다