[백준] 2751. 수 정렬하기 2

❕ 문제

백준 2751. 수 정렬하기 2

❕ 코드 리뷰

import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);

        for(int i=0; i<n; i++){
            System.out.println(arr[i]);
        }

    }
}

❗결과는 시간 초과,,

이 문제는 딱 나같은 사람을 저격하는 문제다..
Arrays.sort(); 는 듀얼 피봇 퀵정렬을 사용하기때문에 최악의 경우 시복잡도가 O(n^2) 라는 것이다.

❕ 새로운 코드 리뷰

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {

        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 i : list){
            sb.append(i).append("\n");
        }
        System.out.println(sb);

    }
}

‼️ 새롭게 생각한 방법은

일반 배열을 ArrayList로 바꿔 Colletions.sort()를 사용했다.