class2 - 2751번 수 정렬하기2 (자바)

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

 

해당 문제를 Arrays.sort 써서 했더니 실버5 문제임에도 불구하고 정답이 나와버려서 너무 허무했다.

그래서 다른 풀이 방법을 찾아봤다.

이 문제는 Collections.sort()를 쓰면 더 빠르게 풀수있다.

 

문제에서 사용하는 개념

함수	알고리즘	평균 시간복잡도	최악 시간복잡도
Arrays.sort()	dual-pivot Quicksort	O(nlogn)	O(n2)
Collections.sort()	hybrid sorting algorithm (= Timsort)  (Timsort = 합병정렬 + 삽입정렬)	합병정렬 : O(nlogn)  삽입정렬 : O(n)	합병정렬 : O(nlogn)  삽입정렬 : O(n2)

 

https://docs.oracle.com/javase%2F7%2Fdocs%2Fapi%2F%2F/java/util/Collections.html

이런식으로 쓸 수 있다.

 

풀이

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String[] args) {
		try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            
            int num = Integer.parseInt(br.readLine());
            List<Integer> arr = new ArrayList<>();
            
            for(int i = 0; i < num; i++) {
                arr.add(Integer.parseInt(br.readLine()));
            }
            
            Collections.sort(arr);
            
            for(int val : arr) {
                bw.write(String.valueOf(val)+"\n");
            }
            
            br.close();
            bw.flush();
            bw.close();
		}
		catch (IOException e) {
          System.out.println("IOException 발생");
		}
		
	}
	
}