백준 2751번 : 수 정렬하기2 - 시간초과 문제해결 - Collections.sort() 사용하기

 

수의 개수 N이 범위가 1부터 100만까지 굉장히 크므로, 처음에는 당연히 가장 빠른 '퀵정렬'을 사용하면 되겠다고 생각했다. 

 

하지만, 내가 잊고 있었던 한 가지 사실... 최악의 경우 퀵 정렬의 시간 복잡도는 Θ(n^2) 이라는 점.

 

Java8 기준으로 Arrays.sort()는 퀵 정렬을 사용하므로 이 메소드를 사용하면 안된다.

 

그렇다면 ??

 

## Collections.sort() 를 이용해보자. 

- 합병 및 삽입정렬 알고리즘을 사용한다. (Tim 정렬) 

합병정렬의 경우, 최선/최악 모두 O(nlogn) 을 보장하고,

삽입정렬의 경우, 최선 O(n), 최악 O(n^2) 이다.

그리고 두 정렬 모두 안정정렬(stable sort) 이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	
	public void solution() {
		Scanner kb = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int n = kb.nextInt();
		
		ArrayList<Integer> list = new ArrayList<>();
		
		for(int i=0;i<n;i++) {
			list.add(kb.nextInt());
		}
		Collections.sort(list);
		
		for(int i=0;i<list.size();i++) {
			sb.append(list.get(i)).append('\n');
		}
		System.out.println(sb);
		
	}
	
	public static void main(String[]args) {
		new Main().solution();		
	}
}

 

여기서 봐야할 점은

 

1. 출력할 때 System.out.print()가 아닌, StringBuilder 를 사용했다.

- 아니면 시간초과가 난다. 이외에도 BufferedWriter를 이용하여 출력 가능하다.

 

2. StringBuilder 를 처음 사용해보는데 사용법 알아두기!

StringBuilder sb = new StringBuilder();

sb.append(list.get(i));

 

for 문 부분을 저렇게 하지 않고 아래 방법으로도 가능하다.

for(int v : list) {

  sb.append(v).append('\n');

}

 

cf. https://st-lab.tistory.com/106