[백준] 2751 : 수 정렬하기 2 JAVA 풀이

문제 제목 아래의 설명란 같은 곳에 언어에 내장된 함수를 쓰는 걸 추천한다기에

Arrays.sort()를 썼는데 시간초과가 나왔다.

 

코드는

1. N을 입력받는다.

2. N개의 수를 입력받아 배열에 저장한다

3. Arrays.sort()로 정렬한다.

4. System.out.println()으로 배열의 값을 출력한다.

이렇게 구성했는데 4번에서 시간이 오래 걸리는 게 아닌가 하고

StringBuilder를 사용했더니 어찌저찌 통과가 되긴 했다.

 

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
      
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(arr);
        
        StringBuilder sb = new StringBuilder();
        for(int val : arr){
            sb.append(val).append('\n');
        }
        System.out.print(sb);
    }
}

이 Arrays.sort()는 dual-pivot Quicksort를 써서

평균적으로는 시간복잡도가 O(nlogn)이지만

최악의 경우에는 O(n^2)라고 한다.

 

이것보다 더 빠르게 정렬을 수행할 수 있는 메서드가 Collections.sort()이다.

Collections.sort()는 Timsort인데, 

Timesort는 합병정렬의 최악의 경우와 삽입정렬의 최선의 경우를 섞은 알고리즘으로

O(n)~O(nlogn)을 보장한다는 장점이 있다.

이를 사용하려면 배열이 아닌 List 계열의 자료구조를 사용해 정렬해야 한다.

 

정렬 메서드와 알고리즘에 대한 내용을 참고한 포스트 ↓

 

https://st-lab.tistory.com/106

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

 

위에서 언급한 Collections.sort()를 이용한 코드는 다음과 같다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
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));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();
      
        for(int i=0;i<N;i++){
            list.add(Integer.parseInt(br.readLine()));
        }
        
        Collections.sort(list);
        
        StringBuilder sb = new StringBuilder();
        for(int val : list){
            sb.append(val).append('\n');
        }
        System.out.print(sb);
    }
}