백준_수 정렬하기 3(10989)

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

10989번: 수 정렬하기 3

 

데이터가 천 만개이고, 데이터의 범위는 10,000 보다 작거나 같은 자연수의 데이터들을 일일이 정렬하면 시간이 엄청나게 걸립니다.

 

물론 Arrays.sort를 사용하여 풀 수는 있습니다. 하지만 아슬하게 통과하게 됩니다.

(사실 최악의 경우 시간복잡도가 O(n^2)까지 나오게 되는데 이번 문제는 저격데이터는 없는거 같습니다.)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(arr);
		
		for (int j = 0; j < N; j++) {
			sb.append(arr[j]).append('\n');
		}
		
		System.out.println(sb);
	}
}

 

기본적으로 이 문제에서는 입출력의 성능이 좋은 것을 택합니다.

Scanner로 쓰면 내부적으로 자체 정규식 검사 과정에서 시간이 소요되기 때문에 '시간 초과'가 발생합니다.

그렇기 때문에 BufferedReader를 사용합니다.

출력도 BufferedWriter 또는 StringBuilder를 이용하여 출력해야 합니다.

 

 

배열에서 모든 원소를 입력받아 저장하고 Arrays패키지에 있는 sort()를 사용하여 정렬을 합니다

Arrays.sort() 의 경우 dual-pivot Quick sort알고리즘을 사용합니다.

평균 O(nlogn)의 시간복잡도를 보이지만 최악의 경우 O(n^2)로 좋지 않은 성능이 될 수 있습니다.