[백준] 2751번 : 수 정렬하기 2 in python 파이썬 :: merge sort

파이썬으로 백준풀기 :: 2751번 수 정렬하기 2

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

---

코드

v = [int(input()) for i in range(int(input()))] # 입력
 
# merge sort
def merge(left, right) :
    v=list()
    i=0;j=0
    while(i<len(left) and j<len(right)) :
        if left[i]<=right[j] :
            v.append(left[i])
            i+=1
        else :
            v.append(right[j])
            j+=1
    if i==len(left) : v = v + right[j:len(right)]
    if j == len(right): v = v + left[i:len(left)]
    return v
 
def merge_sort(v) :
    if len(v) <= 1 : return v
    m = len(v)//2
    left = merge_sort(v[0:m])
    right = merge_sort(v[m:len(v)])
    return merge(left, right)
 
m = merge_sort(v)
print(*m, sep="\n")

---

이 문제는 2750번 수 정렬하기 와 달리 O(nlogn) 알고리즘으로 풀어야 한다.

즉, O(n^2) 인 삽입정렬, 버블정렬이 아닌 merge sort/ heap sort로 풀어야 한다.

여기서도 주의할 점은 똑같은 코드라도 python3 으로 제출하면 안되고 pypy3으로 제출해야한다.

python 기본 내장함수로는 다음과 같이 풀 수 있다.

이 역시 pypy3으로 제출해야 한다.

v = [int(input()) for i in range(int(input()))] # 입력
print("\n".join(map(str,sorted(v))))