[백준] 2751번 : 수 정렬하기 2 (파이썬)

문제

나의 답안

### sorted 사용
import sys
input=sys.stdin.readline

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

for i in range(n):
    li.append(int(input()))

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

파이썬 내장함수인 sorted를 사용해서 풀어주었다.(sort도 가능하다. sort는 원 배열까지 수정, sorted는 원배열 값에 영향을 끼치지 않는다.)

합병정렬로 풀기

### 합병정렬(nlogn)
import sys
input=sys.stdin.readline

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

for i in range(n):
    li.append(int(input()))

def sort(arr):
    if len(arr)<2:
        return arr
    
    mid=len(arr)//2
    left=sort(arr[:mid])
    right=sort(arr[mid:])

    return merge(left,right)
    
def merge(left,right):
    new_list=[]
    i=0
    j=0
    
    while (i<len(left)) & (j<len(right)):
        if left[i]>right[j]:
            new_list.append(right[j])
            j+=1
        else:
            new_list.append(left[i])
            i+=1
    while (j<len(right)):
            new_list.append(right[j])
            j+=1
    while (i<len(left)):
            new_list.append(left[i])
            i+=1
    return new_list
    
for i in sort(li):
    print(i)

합병정렬로 풀었는데 첫 제출에선 틀렸다.(j를 i로 잘못썼다..ㅎ)

합병정렬은 분할 정복 방식으로, 배열을 반으로 나눈 후 이를 기준으로 왼쪽을 정렬 left=sort(arr[:mid]), 오른쪽을 정렬 right=sort(arr[mid:]) 한다.
이후 정렬한 배열을 합병한다. merge(left,right)
오름차순으로 합병을 진행하는데, 오른쪽 값이 왼쪽 값보다 작다면 새 배열(new_list)에 오른쪽 값을 추가하고, 숫자를 증가시킨다.

if left[i]>right[j]:
	new_list.append(right[j]) 
	j+=1

왼쪽 값도 동일하게 한다.

else:
	new_list.append(left[i])
    i+=1

이후 정렬하고 남은 나머지 값을 배열에 추가하고, 배열을 반환해준다.

while (j<len(right)):
            new_list.append(right[j])
            j+=1
    while (i<len(left)):
            new_list.append(left[i])
            i+=1
    return new_list