[Baekjoon] 수 정렬하기 2 / Python, 파이썬 / 2751

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

2751번: 수 정렬하기 2

문제 설명

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

입력

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

출력

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

예제 입력 1

5
5
4
3
2
1

예제 출력 1

1
2
3
4
5

문제 풀이

병합 정렬 ( Merge Sort )

import sys

input = sys.stdin.readline

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]
            j += 1
            k += 1
    elif j == len(right):
        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
    return array

N = int(input())
result = []

for _ in range(N):
    result.append(int(input()))

result = merge_sort(result)

for i in result:
    print(i)

Sorted 사용 ( 시간 더 빠름 )

import sys

input = sys.stdin.readline

N = int(input())
result = []

for _ in range(N):
    result.append(int(input()))

for i in sorted(result):
    print(i)