[백준/Python] 2751번: 수 정렬하기 2

📖  문제 링크

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

2751번: 수 정렬하기 2

 

👩‍💻  문제풀이

정석 병합 정렬(MergeSort) 알고리즘을 구현하여 파이썬으로 제출했으나 시간 초과가 되었다. 

그래서 input을 sys 라이브러리를 불러와 구현했지만 그래도 시간초과! 

 

검색해보니 PyPy3로 제출하라는 말이 있어 시도해보았더니 빠르진 않았지만 통과가 되었다. 

 

 

sort함수로 구현한 코드는 Python 병합정렬 제출과 비슷한 속도가 나왔고, PyPy3에서는 절반가량 속도가 줄었다.

 

 

 

 

✅  최종 코드

 

추후 다시 이 문제를 시도할 때 도움이 될까하여 정석으로 푼 코드와 sort함수를 사용한 코드를 모두 올린다.

# <병합정렬 알고리즘 활용 풀이>

import sys

n = int(input())
array = []
for i in range(n):
    array.append(int(sys.stdin.readline()))

def mergeSort(array):
    if len(array) <= 1:
        return array

    middle = len(array)//2
    left = mergeSort(array[:middle])
    right = mergeSort(array[middle:])

    return merge(left, right)
    

def merge(left, right):
    sorted_list = [] * n
    i = j = 0

    while i<len(left) and j<len(right) :
        if left[i] < right[j] :
            sorted_list.append(left[i])
            i+=1
        else:
            sorted_list.append(right[j])
            j+=1

    if i<len(left):
        sorted_list += left[i:]
    if j<len(right):
        sorted_list += right[j:]

    return sorted_list


array = mergeSort(array)

for i in range(n):
    print(array[i])

 

 

# <파이썬 sort함수를 활용한 풀이>
import sys

n = int(input())
array = []
for i in range(n):
    array.append(int(sys.stdin.readline()))

array.sort()
for i in range(n):
    print(array[i])

#sys를 사용하면 출력이 더 빠를까 싶어 시도해본 코드!
# for i in sorted(array):
#     sys.stdout.write(str(i) + '\n')