[JAVA] 백준 2751번 - 수 정렬하기 2 (Tim sort)

 

 

<코드 - Scanner + Collections.sortr>

import java.util.*;
public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		StringBuffer sb = new StringBuffer();
		
		int N = sc.nextInt();
		ArrayList<Integer> list = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			list.add(sc.nextInt());
		}	
		
		Collections.sort(list);

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

 

<코드 - BufferedReader + Collections.sort>

import java.util.*;
import java.io.*;
public class Main {
	
	static char chess[][];
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		
		int N = Integer.parseInt(br.readLine());
		ArrayList<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+"\n");
		}
		
		System.out.println(sb);
	}
}

데이터가 최대 100만 개이므로 확실히 Scanner로 입력을 받는 것보다 BufferedReader로 받는 것이 훨씬 빠른 것 같습니다.

 

 

풀이 방법

 

Arrays.sort()는 dual-pivot Quicksort 알고리즘을 사용하며 평균 시간복잡도가 O(nlogn)이며 최악의 경우 시간복잡도는 O(n²)이 됩니다. 입력의 개수가 최대 1,000,000개이므로 Arrays.sort()를 사용하면 시간초과가 발생할 수 있습니다.

 

Collections.sort()는 Tim sort 알고리즘을 사용하며 merge(합병) , Insertion(삽입) 알고리즘의 장점들만 뽑은 알고리즘입니다.

알고리즘	최선의 경우	최악의 경우
합병정렬(merge sort)	O(nlogn)	O(nlogn)
삽입정렬(Insertion sort)	O(n)	O(n²)
팀정렬(Tim sort)	O(n)	O(nlogn)

 

Tim sort를 이용하면 시간복잡도가 O(n)~O(nlogn)로 보장되므로 100만 개의 데이터를 제한시간 내에 처리할 수 있고 Collections.sort()를 사용하므로 일반적인 배열이 아닌 List 계열(ArrayList, LinkedList 등..)의 자료구조를 사용하여야 합니다.

 

 

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

2751번: 수 정렬하기 2