백준 2751번 수 정렬하기 2

문제

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

입력

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

출력

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

 

 

 

난 이 문제를 처음에  수가 100만 개나 입력되기 때문에 시간복잡도가 효율적인 정렬을 사용하기 위해

Quick Sort를 이용해서 풀려고 했었다.

 

 

 

 

Quick Sort

---

 

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


public class Main {
 public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] numbers = new int[N];

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            if (!contains(numbers, i, num)) {
                numbers[i] = num;
            }
        }
        br.close();

        numbers = Arrays.copyOf(numbers, N); // 중복을 제거한 배열의 크기로 재조정
        quickSort(numbers, 0, numbers.length - 1);

        for (int num : numbers) {
            if (num != 0) {
                System.out.println(num);
            }

        }
    }

    private static boolean contains(int[] arr, int length, int target) {
        for (int i = 0; i < length; i++) {
            if (arr[i] == target) {
                return true;
            }
        }
        return false;
    }
    private static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);
            quickSort(arr, left, pivot - 1);
            quickSort(arr, pivot + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left - 1;

        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, right);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

그러나 결과는 시간 초과

 

찾아보니까 Quick Sort 같은 경우는 최악의 경우 시간복잡도가 O(n^2) 일 수 있기 때문에 

Quick Sort  가 아닌 병합정렬을 사용해야 했다.

 

 

 

아래는 병합정렬을 사용한 코드이다.

 

 

 

 

Merge Sort

---

import java.io.*;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());


        int[] nums = new int[N];

        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }

        mergeSort(nums);



        for (int num : nums) {
            bw.write(num + "\n");
        }

        bw.flush();
        bw.close();
        br.close();

    }

    static void mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return; // 배열이 비어있거나 원소가 하나 이하인 경우 정렬할 필요가 없으므로 종료
        }

        int[] tempArray = new int[array.length];
        mergeSort(array, tempArray, 0, array.length - 1);
    }

    static void mergeSort(int[] array, int[] tempArray, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2; // 중간 인덱스 계산

            mergeSort(array, tempArray, left, mid); // 왼쪽 부분 배열 정렬
            mergeSort(array, tempArray, mid + 1, right); // 오른쪽 부분 배열 정렬

            merge(array, tempArray, left, mid, right); // 정렬된 두 부분 배열 병합
        }
    }

    static void merge(int[] array, int[] tempArray, int left, int mid, int right) {
        // 두 부분 배열의 시작 인덱스 설정
        int leftStart = left;
        int rightStart = mid + 1;
        int tempIndex = left; // 임시 배열의 인덱스

        // 두 부분 배여을 비교하여 적은 값을 임시 배열에 병함
        while (leftStart <= mid && rightStart <= right) {
            if (array[leftStart] <= array[rightStart]) {
                tempArray[tempIndex] = array[leftStart];
                leftStart++;
            } else {
                tempArray[tempIndex] = array[rightStart];
                rightStart++;
            }
            tempIndex++;
        }
        // 왼쪽 부분 배열의 나머지 원소를 임시 배열에 복사
        while (leftStart <= mid) {
            tempArray[tempIndex] = array[leftStart];
            leftStart++;
            tempIndex++;
        }

        // 오른쪽 부분 배열의 나머지 원소를 임시 배열에 복사
        while (rightStart <= right) {
            tempArray[tempIndex] = array[rightStart];
            rightStart++;
            tempIndex++;
        }

        // 임시 배열의 내용을 원래 배열에 복사
        for (int i = left; i <= right; i++) {
            array[i] = tempArray[i];
        }
    }
}

결과는 통과

 

Merge Sort 는 시간 복잡도가 어떠한 경우에도 O(n log n) 이기 때문에 Quick Sort와 다르게 안정적이면서도 효율적인 시간복잡도를 구현할 수 있다.

 

 

위 문제를 풀면서 여러가지 종류의 정렬들을 찾아보고 공부해서 정리해 봤다.

아래는 그 링크이다.

https://cordcat.tistory.com/129

ㄴ 여러 가지 정렬들의 시간복잡도 및 사용되는 상황들 정리글