백준 #2751 / 수 정렬하기 2(우선순위 큐, Merge, Quick Sort)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	17288	6020	3981	36.516%

문제

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

입력

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

출력

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

---

이번 문제는 너무 쉬우니까, 실행시간 비교 및 여러가지 방법을 이용해서 포스팅해보려고 한다.

[Method 1] 우선순위 큐를 이용하는 방법.

- 단순히 값들을 입력 받고, 우선순위 큐에 넣고, poll하는 순서대로 출력한다.

[우선순위 큐 - Code]

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
 
public class boj_2751 {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine().trim());
        
        for(int i=0;i<N;i++)
            pq.add(Integer.parseInt(br.readLine().trim()));
        
        while(!pq.isEmpty())
        {
            sb.append(pq.poll()+"\n");
        }
        System.out.println(sb);
    }
}
 

- ..... 메모리랑 실행시간 실화냐... 패스...

[Method 2] Merge-Sort (합병 정렬)

[Code]

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Merge_Sort {
    static int result[];
    public static void mergeSort(int left,int right,int[] arr) {    // 숫자열을 가져와서 1개 단위로 쪼개는 행위
        int mid;
        if(left<right) {
            mid = (left+right)/2;
            mergeSort(left,mid,arr);    // 총 8개의 원소를 갖는 배열이 있다면, 맨 앞의 0번째 1번째 인덱스가 하나로 쪼개질 때까지 쪼갠다.
            mergeSort(mid+1,right,arr);
            merge(left,mid,right,arr);    // 다 쪼개면, 하나로 합친다.
        }
    }
    public static void merge(int left,int mid,int right,int[] arr) {
        int l = left;    // 쪼개진 첫 번째 배열의 첫 인덱스
        int m = mid+1;    // 쪼개진 두 번째 배열의 첫 인덱스
        int k = left;    // 새로 삽입될 배열의 첫 인덱스
        
        while(l<=mid || m<=right) {    // 쪼개진 두 배열의 원소를 비교해가면서 새로운 배열에다가 삽입한다.
            if(l<=mid && m<=right) {    // 두 배열 모두 비교가 필요한 원소가 남아있다면
                if(arr[l]<=arr[m]) result[k] = arr[l++];    // 첫 번째 배열과 두 번째 배열의 현재 인덱스를 비교, 더 작은 부분을 삽입한다.
                else result[k] = arr[m++];
            }
            else if(l<=mid && m > right)     // 두 번째 배열은 비교할 원소가 남아 있지 않은경우
                result[k] = arr[l++];
            else result[k] = arr[m++];        // 첫 번째 배열은 비교할 원소가 남아 있지 않은 경우
            k++;
        }
        for(int i=left;i<right+1;i++)    // 쪼갠
            arr[i] = result[i];
    }
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine().trim());
        result = new int[N];
        int[] arr = new int[N];
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(br.readLine().trim());
        
        mergeSort(0,N-1,arr);
        
        for(int i=0;i<N;i++)
            sb.append(result[i]+"\n");
        System.out.println(sb);
    }
}

- 확실히 메모리와 실행시간이 확 줄어들긴 했는데, 백준 1위와의 격차가 약 400MS...

[Method 3] Quick-Sort(퀵소트)

[Code]

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class boj_2751 {
    
    public static void Swap(int[] arr,int first,int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
    public static void QuickSort(int[] arr,int left,int right) {
        if(left >= right) return;
        int pivot = arr[right];
        int l = left;
        int r = right-1;
        
        while(l <= r) {    // 교차하기 전까지 진행
            while(l<=r && arr[l]<=pivot) l++;
            while(l<=r && arr[r]>=pivot) r--;
            if(l<r) Swap(arr,l,r);
        }
        Swap(arr,l,right);
        QuickSort(arr,left,l-1);
        QuickSort(arr,l+1,right);
    }
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine().trim());
        int arr[] = new int[N];
        
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(br.readLine().trim());
        
        QuickSort(arr,0,N-1);
        
        for(int i=0;i<N;i++)
            sb.append(arr[i]+"\n");
        
        System.out.println(sb);
    }
}

- 예상한 결과지만 진짜 별 차이 없다. 병합정렬이나 퀵정렬 둘다 O(nlogn)이기 때문에...

그냥 이 문제는 풀면서 병합정렬이랑 퀵정렬이 손에 익은걸로 만족한다.