[백준] 2751번. 수 정렬하기 2 (Java)

[문제 바로가기] https://www.acmicpc.net/problem/2751

문제

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

입력

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

출력

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

---

풀이

처음에는 '수 정렬하기 1'과 동일하게 Arrays.sort()로 해결이 가능한 줄 알고 Arrays.sort()로 작성하고 제출했지만 시간 초과가 발생했다.
그리고 다시 문제를 읽다가 발견한 내용..

Arrays.sort()는 primitive arrays에 대해 Dual-Pivot Quicksort 을 수행한다.
평균 시간복잡도가 O(nlogn)이지만 최악의 경우 시간복잡도는 O(n^2)

즉, 이 문제는 O(n^2) 를 못하게 하는 문제이다.

일단 문제를 풀기 위해서는 최악의 경우에도 O(nlogn) 을 보장하거나, O(n) 에 가까운 정렬 알고리즘으로 풀어야 해서 Collections.sort()를 사용해보았다.

Collections.sort()은 Object type arrays에 대해 Merge Sort 보다 향상된 Tim Sort 를 수행한다.
Tim sort란 합병정렬의 최악의 경우와 삽입정렬의 최선의 경우를 짬뽕한 알고리즘으로 시간복잡도는 O(n) ~ O(nlogn) 을 보장한다,

다만, Collectoins.sort()는 일반적인 배열로 사용할 수 없고 리스트를 이용해야 한다.

그래서 신나게 룰루랄라 Collecionts.sort()를 넣고 백준에 넣어봤는데 또 시간초과가 발생했다!!
이유가 뭐지 싶었는데 발견한 사실.. 출력 방법이 잘못되었다.

출력으로 Stringbuilder를 사용하는 것이 성능면에서 더 좋다.

Stringbuilder는 String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아니라 기존의 데이터에 더하는 방식을 사용하기 때문에 속도도 빠르며 상대적으로 부하가 적다.

이제 제출하면 코드가 정상적으로 작동한다.

---

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int N = sc.nextInt();
		
		ArrayList<Integer> list = new ArrayList<>();
	
		for(int i = 0; i < N; i++) {
			list.add(sc.nextInt());
		}
		
		Collections.sort(list);

		for(Integer c : list) {
			sb.append(c).append("\n");
		}
		
		System.out.println(sb);
	}
}