[정렬] 백준 2751번 수 정렬하기2(Java)

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

2751번: 수 정렬하기 2

📚 문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력	예제 출력
5 5 4 3 2 1	1 2 3 4 5

 

📝 문제 해결

입력받은 수를 오름차순으로 정렬하는 아주 기본 문제

 

💻 코드

import java.util.*;

public class Main{
    public static void main(String[] args){
        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]);
        }
    }
}

..롸?

동일한 코드로 작성한 1번은 무사통과되었는데
2번은 시간초과됨

Arrays.sort()는 Dual-Pivot Quicksort 을 수행하는 정렬 알고리즘으로,
평균 시간복잡도가 O(nlogn)이지만 최악의 경우 시간복잡도는 O(n^2)임

Collections.sort()은 Tim Sort 를 수행하는 정렬 알고리즘으로,
O(n)~O(nlogn) 의 시간복잡도를 보장한다.

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i =0; i<n; i++){
           arr.add(sc.nextInt());
        }
       
        Collections.sort(arr);
        
         for(int i =0; i<n; i++){
            System.out.println(arr.get(i));
        }
    }
}

System.out.println()을 사용할 때마다 바로 출력하면 시간 초과가 날 수 있다.
따라서 Stringbuilder로 모았다가 한번에 출력하면 속도도 빠르며 상대적으로 부하가 적다.

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i =0; i<n; i++){
           arr.add(sc.nextInt());
        }
       
        Collections.sort(arr);
        StringBuilder sb = new StringBuilder();
         for(int i =0; i<n; i++){
           sb.append(arr.get(i) + "\n");
        }
        
        System.out.println(sb);
    }
}

 

📌 기억할 점

 Arrays.sort()와 Collections.sort()의 시간복잡도 비교

	정렬방식	시간복잡도
Array sort()	Dual pivot Quick sort	- 평균 : O(nlogn) - 최악 : O(n^2)
Collections sort()	timesort (삽입정렬 + 합병정렬)	- 평균 : O(nlogn) - 최악 : O(logn)

 

 

반복해서 출력해야하는 경우엔 StringBuilder를 사용하자!