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

처음 접근방법 :

배열에 입력값을 저장한 후 Arrays.sort를 사용하여 정렬하면 될 것이라고 생각했다.

문제점 :

시간초과

해결 방법 :

Arrays.sort가 아닌 Collections.sort를 사용 + System.out.println대신 BufferedWriter를 사용

• Arrays.sort와 Collections.sort의 차이점
  https://www.acmicpc.net/board/view/31887

Arrays.sort는 dual-pivot-algorithm을 사용하여 평균적으로는 시간복잡도가 O(nlogn)이지만 최악의 경우 O(n^)이다.

반면 Collections.sort는 합병정렬과 삽입정렬이 합쳐진 Hybrid stable sorting algorithm을 사용하여 O(n) ~ O(nlogn)의 시간복잡도를 가진다.

따라서 최악의 경우를 고려하여 Collections.sort로 코드를 작성해야 한다.

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

public class No2751_수_정렬하기2 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int tc = Integer.parseInt(br.readLine());
		String s="";
	
		ArrayList<Integer> arr = new ArrayList<Integer>();
		for (int i=0;i<tc;i++) {
			arr.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(arr);
		
		for (int i=0;i<tc;i++)
			bw.write(arr.get(i)+"\n");
		// TODO Auto-generated method stub
		
		bw.flush();
		bw.close();
		br.close();
		}
	}