[백준 2751번: 수 정렬하기2]자바 문제풀이(collections.sort)

"시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다."

문제 설명란에 힌트가 나와있다. 이번에는 O(n^2)이 아닌 O(nlogn)이어야한다. 

정렬	평균	최상	최악
선택정렬	n^2	n^2	n^2
버블정렬	n^2	n^2	n^2
삽입정렬	n^2	n	n^2
셸 정렬	n^1.5	n	n^2
퀵 정렬	nlogn	nlogn	n^2
힙 정렬	nlogn	nlogn	nlogn
병합정렬	nlogn	nlogn	nlogn

병합 정렬, 힙 정렬은 나중에 공부하고 지금은 설명란의 추천대로 자바 안에 내장된 정렬 함수를 사용해보았다.

 

*Collections.sort : 리스트 정렬로서 다중 정렬에 해당한다.

자바 내장 정렬 중 내가 알고 있는 정렬은 Arrays.sort()와 Collections.sort()이다.

Arrays.sort는 배열을 정렬하는 것이고 Collections.sort는 리스트를 정렬해야한다. 

 

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder st = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Integer> arr = new ArrayList<>();
		for(int i=0; i<N; i++)
			arr.add(Integer.parseInt(br.readLine()));
		
		Collections.sort(arr);
		
		for(int i=0; i<arr.size(); i++)
			st.append(arr.get(i)).append('\n');
		
		System.out.print(st);
	}

}

시간을 줄이기 위해서 Scanner보다는 BufferedReader를 사용했다. 

그리고 일일히 다 출력하기 보다는 StringBuilder을 이용하여 정렬 결과를 한번에 출력했다.