[백준] 2751 수 정렬하기 2

GitHub - DAWUNHAN/Algorithms-and-DataStructure: Algorithms and DataStructure with Python

문제 해설

• n개의 숫자를 입력 받은 뒤, 순서대로 출력하라.
• 데이터 개수가 최대 1,000,000개 일 때, 시간 복잡도 o(NlogN)의 정렬 알고리즘을 이용해야 한다.

 

병합 정렬을 직접 구현하는 방법

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[i]:
            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())
array = []

for _ in range(n):
    array.append(int(input()))
    
array = merge_sort(array)

for data in array:
    print(data)

 

파이썬 내장 함수로 구현하는 방법

n = int(input())
array = []

for _ in range(n):
	array.append(int(input()))
    
array = sorted(array)

for data in array:
	print(data)

 

 

GitHub - DAWUNHAN/Algorithms-and-DataStructure: Algorithms and DataStructure with Python