백준 | 정렬 섹션 - 2751번. 수 정렬하기 2

2751번. 수 정렬하기 2

• 첫 시도는 Arrays.sort() 사용했는데 시간 초과가 떴다.
• 이 문제는 O(n)에 가까운 정렬 알고리즘을 사용해야 한다.

첫 시도

import java.util.Arrays;
import java.util.Scanner;

/* 2751번. 수 정렬하기 2 
 * */
public class Main {


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        int n =kb.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) arr[i] = kb.nextInt();

        Arrays.sort(arr);

        for(int x: arr) System.out.println(x);
    }

}

두 번째 시도

• Scanner + Collections.sort 사용
• String 보다 StringBuilder 사용하면 기존의 객체에 누적 더하니 속도 빠르다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/* 2751번. 수 정렬하기 2 
 * */
public class Main {


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int n =kb.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();

        for(int i=0; i<n; i++) arr.add(kb.nextInt());

        //정렬
        Collections.sort(arr);


        for(Integer c : arr) {
            sb.append(c).append("\n");
        }
        System.out.println(sb);
    }
}

---