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

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

2751번: 수 정렬하기 2

 

 

[풀이 코드]

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())
array = []
for _ in range(n):
    array.append(int(input()))

print(*merge_sort(array), sep="\n")

- 병합 정렬, 퀵 정렬을 제출해봤지만 퀵 정렬은 메모리 초과가 되었다. 아무래도 퀵 정렬은 정렬이 되어있는 상태라면 시간 복잡도가 현저히 안 좋아져서 그런 것 같다.

 

- 거의 까먹었던 병합정렬을 정리해보았다.

• 절반씩 합치면서 정렬하면, 전체 리스트가 정렬
• 시간복잡도 O(NlogN)을 보장

 

[두 번째 풀이 코드]

# sorted() 활용
n = int(input())
array = []
for _ in range(n):
    array.append(int(input()))
array = sorted(array)
print(*array, sep="\n")

- 파이썬에 내장되어 있는 기본 정렬 함수인 sorted를 활용했다. 실제로 코테를 볼 땐 위처럼 풀어야 효율적일 것 같다..