[Baekjoon] 2751 수 정렬하기 2

[Silver V] 수 정렬하기 2 - 2751

문제 링크

성능 요약

메모리: 324776 KB, 시간: 2580 ms

분류

정렬(sorting)

문제 설명

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

입력

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

출력

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

---

알고리즘 과정

이 문제는 단순하게 Arrays.sort()를 사용하면 시간복잡도가 $O(n^2)$가 걸리게 되는 저격 데이터가 있다고 다른 블로그에서 보았다.

그래서 이번에는 Collections.sort()를 사용할 것이다. 이 방법은 시간복잡도 평균이 $O(nlog(n))$이고 최악의 경우에도 $O(nlog(n))$을 가지게 된다.

저번 블로그 포스팅과 이번 포스팅때 사용한 정렬의 시간을 표로 작성해보자면

정렬	시간 복잡도
Collections.sort	평균 : $O(nlog(n))$ 최악 : $O(nlog(n))$
Arrays.sort	평균 : $O(nlog(n))$ 최악 : $O(n^2)$

Collections.sort()같은 경우에는 Timsort() 정렬 기법으로 삽입 정렬과 합병 정렬을 합쳐서 만든 것이라고 한다.

Timsort() 정렬이 뭔지 모르겠어서 찾아봤더니 아직까지 뭔 소린지 잘 모르겠다 :) 나중에 시간이 된다면 정렬에 관하여 정확하게 알고 포스팅을 따로 해야겠다.

sort() 메소드의 매개변수 타입은 List<T>로 제네릭 타입을 받고 있다고 한다.

정렬 알고리즘을 풀 때는 시간을 줄이기 위하여 BufferRead나 StringBuilder를 사용하는 경우가 많은 것 같다. 이번 문제를 풀 때도 StringBuilder를 사용하여 풀 것이다.

이제 문제를 어찌 풀어야하나 생각해본다면 순서대로 일단 list를 만들고 list.add()를 사용하여 숫자들을 추가하고 Collections.sort()를 이용하면 정렬이 된다.

마지막으로 StringBuilder를 이용하여 정렬한 숫자를 리스트에서 꺼내서 한 개씩 추가해주면 마무리된다.

---

코드