Baekjoon 문제 풀기 (2751번 : 수 정렬하기 2) Java

2751번 : 수 정렬하기 2

1. 문제읽기

---

백만의 입력값이 주어졌을 때, 시간초과가 나지 않는 정렬 코드 구현하기

Arrays.sort로 안되면 다른 방법을 생각해보자라고 생각하고 구현했는데 통과했다.

2. 제출 코드

---

BufferedReader와 StringBuilder를 사용해서 Arrays.sort를 사용해도 시간초과가 나지 않은 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ2751 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }
        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();
        for(int i : arr) {
            sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
}

3. 공부할 것

---

Arrays.sort()는 시간복잡도가 최악의 경우 $O(N^2)$으로 자칫 잘못하면 시간초과가 난다고 한다.
안정적으로 통과하려면 Collections.sort()나 Counting sort를 이용해야한다.
Collections.sort()는 최악의 경우 O(nlogn)이기 때문에 Arrays.sort()보다 낫다.
나는 배열을 쓰는 것이 더 기초(?)적인 것이기 때문에 Arrays.sort()가 더 빠른 줄 알았는데 아니었다.
앞으로는 Collections.sort()를 더 사용해야겠다.
아래는 Collections.sort()를 사용한 코드.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BOJ2751 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        List<Integer> arr = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            arr.add(Integer.parseInt(bf.readLine()));
        }
        Collections.sort(arr);
        StringBuilder sb = new StringBuilder();
        for(int i : arr) {
            sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
}