[백준 알고리즘][자바] 2751번 : 수 정렬하기 2

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

2751번: 수 정렬하기 2

 

이번 문제는 자바에 내장되어 있는 정렬 함수를 사용하여 푸는 문제이다.

자바에 내장되어 있는 정렬 함수는 Arrays.sort() 와 Collections.sort()가 있다.(자바 8기준)

 

2022.04.30 - [Programming/Java] - [Java] 자바 내장 정렬 함수 - Arrays.sort()

[Java] 자바 내장 정렬 함수 - Arrays.sort()

 

Arrays.sort()를 사용하여 문제를 풀면 시간초과가 난다.

앞서 작성한 글에서 Arrays.sort()의 시간 복잡도는 O(nlogn)이지만 최악의 경우 O(n^2)가 될 수 있다.

이 문제는 데이터 속에 O(n^2)가 걸리는 데이터가 있어 최악의 경우 O(nlogn)을 보장해야한다.

 

따라서 두번째 내장 정렬 함수인 Collections.sort()를 사용해야한다.

 

Collections.sort()는 TimSort이다.(TimSort에 대해서는 추후에 자세히 다루어 보도록 하겠습니다.)

TimSort는 InsertionSort와 MergerSort를 섞은 정렬 알고리즘이다.

TimSort의 시간 복잡도는 O(nlogn)~O(n)을 보장하기 때문에 이번 문제에서 사용한다.

 

풀이

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 Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for(int i = 0 ; i < N ; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(list);
		
		for(int i : list) {
			bw.write(String.valueOf(i) + "\n");
		}

		br.close();
		bw.flush();
		bw.close();
	}

}