[알고리즘 / 백준] 2751 - 수 정렬하기 2

 

문제는 위와 같으면 주어지는 수의 개수가 1,000,000 개까지 이므로 파이썬이 일반적으로 1초에 20,000,000 번의 연산을 수행한다고 할 때 NlogN 의 시간 복잡도를 가지는 정렬 알고리즘을 통해 문제를 해결할 수 있습니다.

 

NlogN 의 시간 복잡도를 가지는 정렬 알고리즘은 병합 정렬, 퀵 정렬, 힙 정렬 등이 있으며 기본적으로 파이썬에 내장된 sort() 메소드 또한 NlogN 의 시간 복잡도를 가진다고 할 수 있습니다. 

 

먼저, 파이썬에 내장된 함수를 사용하는 코드를 살펴보겠습니다.

from sys import stdin

n = int(stdin.readline())
nums = [int(stdin.readline()) for _ in range(n)]

nums.sort()
print("\n".join(str(n) for n in nums))

 

다음으로 직접 병합 정렬을 구현하여 문제를 해결해보겠습니다.

from sys import stdin


# 병합 정렬 사용하기
def merge_sort(array):
    if len(array) <= 1:
        return array

    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    i, j, k = 0, 0, 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1

    if i == len(left):
        while j < len(right):
            array[k] = right[j]
            k += 1
            j += 1
    elif j == len(right):
        while i < len(left):
            array[k] = left[i]
            k += 1
            i += 1

    return array


n = int(stdin.readline())
nums = [int(stdin.readline()) for _ in range(n)]
nums = merge_sort(nums)
print("\n".join(str(n) for n in nums))

 

다음으로 자바 코드도 살펴보겠습니다. 먼저 자바에서도 기본적으로 제공하는 sort 메소드를 사용하여 구현하겠습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

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

        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            sb.append(nums[i]).append("\n");
        }

        System.out.println(sb);
    }
}

 

직접 병합 정렬을 구현한 자바 코드를 살펴보겠습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

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

        nums = mergeSort(nums);
        for (int i = 0; i < nums.length; i++) {
            sb.append(nums[i]).append("\n");
        }

        System.out.println(sb);
    }

    private static int[] mergeSort(int[] array) {
        if (array.length <= 1) {
            return array;
        }

        int mid = array.length / 2;
        int[] left = new int[mid];
        System.arraycopy(array, 0, left, 0, mid);
        left = mergeSort(left);

        int[] right = new int[array.length - mid];
        System.arraycopy(array, mid, right, 0, right.length);
        right = mergeSort(right);

        int i = 0;
        int j = 0;
        int k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                array[k] = left[i];
                i += 1;
            } else {
                array[k] = right[j];
                j += 1;
            }
            k += 1;
        }

        if (i == left.length) {
            while (j < right.length) {
                array[k] = right[j];
                j += 1;
                k += 1;
            }
        } else if (j == right.length) {
            while (i < left.length) {
                array[k] = left[i];
                i += 1;
                k += 1;
            }
        }

        return array;
    }
}