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

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

2751번: 수 정렬하기 2

 

풀이

사용한 알고리즘 : 정렬

 

풀이전략

문제 자체는 어렵지 않은데 JAVA에서 최적화된 정렬방법 및 입출력을 사용하지 않으면 시간초과가 나오는 문제였다.

 

문자열을 출력할 때, 한 줄 한 줄 출력을 하기보다 StringBuilder를 사용하는 것이 더 효율적이었다.

StringBuilder는 출력해야할 문자열들을 하나로 묶어줬다가 한번에 출력시키는 역할 수행한다.

또한 정렬에서 Arrays.sort() 라이브러리를 사용하면 시간초과가 발생했는데,

Collections.sort() 라이브러리를 사용하면 시간초과가 발생하지 않았다.

이유를 보니 Arrays.sort는 dual-pivot Quicksort 알고리즘을 사용하여 평균 복잡도가 O(nlogn)이지만

최악의 경우 시간 복잡도가 O(n^2)이 나오는 것이 문제였다.

반면에 Collection.sort()는 평균 시간 복잡도가 O(n)이고, 최악의 경우 O(nlogn)으로 Arrays.sort()보다 더 효율적이었다.

 

앞으로 문제 풀이 및 코드를 짤 때, 위의 내용을 상기하여 더 효율적인 코드를 짜야겠다.

 

제출코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
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 Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = 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<N;++i){
            sb.append(arr.get(i)+"\n");
        }
        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
    }
}