[CLASS 2: 정렬] 백준 2751 수 정렬하기(2)

2751번: 수 정렬하기(2)

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

 

# 코드

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    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);
    for (int ele : arr) {
      sb.append(ele).append("\n");
    }
    System.out.print(sb);
    br.close();
  }
}

• java에서 제공하는 Arrays.sort() 메소드를 사용해 정렬했다.
• 시간초과가 나지는 않았지만 예상대로 굉장히 오래 걸렸다.

 

Arrays.sort() 를 사용한 정렬

 

 

이런 문제는 대부분 Arrays.sort를 사용하면 시간초과가 난다고 한다.

Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 사용한다. 물론 평균 시간복잡도가 O(nlogn) 이고 매우 빠른 알고리즘인 것은 맞다. 그러나 최악의 경우 시간복잡도가 O(n2) 일 수 있다는 점을 기억해야한다.

 

 

따라서 Collections.sort() 메소드를 사용하기로 한다.

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    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);
    for (int ele : list) {
      sb.append(ele).append("\n");
    }
    System.out.print(sb);
    br.close();
  }
}

• Collections.sort()를 사용하기 위해서는 List 계열을 데려왔다.
• 처음의 코드에서 달라진 것은 ArrayList 와 Collections.sort() 뿐이다.

 

그런데 사실 유의미한 차이는 아닌 것 같다 (´･ω･`)?

 

 

참고한 블로그는 아래이다.

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