[백준 BOJ 2751번] 수 정렬하기 2

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

2751번: 수 정렬하기 2

 

1. 문제

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

 

---

2. 입력

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

 

5
5
4
3
2
1

---

3. 출력

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

 

1
2
3
4
5

---

4. 풀이

우선, 해당 문제를 다양한 정렬 방식을 이용할 수 있는데 만약 Arrays.sort와 같은 라이브러리 함수를 사용할 시에는 시간 초과 에러가 뜨게 해두었다. Arrays.sort 함수는 dual pivot QuickSort 알고리즘을 사용하는데 평균 시간복잡도는 O(nlogn)이지만 퀵소트 특성 상 최악의 경우엔 시간복잡도가 O(N^2)이다. 그렇기에 다른 방법으로 합병정렬이나 힙정렬, 카운팅정렬 등을 사용할 수 있다. 풀이법은 일반적인 정렬이니 생략한다.

---

5. 소스코드

<합병 정렬>

import java.io.*;

class Main{
    static int [] temp;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int num = Integer.parseInt(br.readLine());
        int [] arr =  new int[num];
        temp = new int[num];
        for(int i=0; i<num; i++) arr[i] = Integer.parseInt(br.readLine());

        mergeSort(arr, 0, num-1);

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

    public static void mergeSort(int[] A, int p, int r){
        int q = (p+r)/2;
        if(p<r){
            mergeSort(A, p, q);
            mergeSort(A, q+1, r);
            merge(A, p, q, r);
        }
        
    }

    public static void merge(int[] A, int p, int q, int r){
        int i = p;
        int j = q+1;
        int k = p;
        while(i <= q && j <= r){
            if(A[i] < A[j]) temp[k++] = A[i++];
            else temp[k++] = A[j++];
        }
        while(i <= q) temp[k++] = A[i++];
        while(j <= r) temp[k++] = A[j++];

        for(int a=p; a<=r; a++) A[a] = temp[a];
    }
}

---

6. 배운 것

아직 힙정렬, 카운팅 정렬 풀이법 올리지 못함