[파이썬python] 백준 2751번 - merge sort

백준 2751번 문제를 풀어봤습니다.

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

2751번: 수 정렬하기 2

문제는 상당히 간단한데, python3으로 제출하니까 계속 시간초과가 뜨더라고요!

다시봤더니 n의 범위가 무려 100만이였네요..ㄷㄷ

그래서 대부분 pypy3로 제출을 하셨더라고요.

2가지 풀이방법을 준비했으니 잘 따라오세요!

---

시간복잡도

n의 범위가 100만(0이 6개)이기 때문에 시간복잡도가 O(NlogN)까지 가능한데, 

log의 밑이 2이기 때문에, 

따라서 1초에 약 2천만 번의 연산 횟수를 할 수 있습니다.

---

풀이방법

1) 병합정렬

순서가 뒤죽박죽인 배열이 있을 때 이를 정렬하기 위해서는 분할과 정복방식을 이용합니다.

1. 데이터를 절반씩 나누어 끝까지 갔다가(분할)

2. 다시 절반씩 합치면서 그 안에서 정렬합니다.(정복)

 

병합 정렬은 분할 단계에서 분할되는 깊이가 로그 N에 비례하고,

각 깊이 별로 분할이 수행되어 합병해야되는 배열의 수는 많아지지만,

총 원소의 수는 N개로 같으므로 각 깊이별로 수행되는 merge의 시간복잡도는 O(N)입니다. 

이를 파이썬으로 구현하면 다음과 같습니다. 

 

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

병합정렬을 이용한 정답) 위에 구현한 merge-sort함수를 이용하면 됩니다!

정답코드)

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())
num = []

for _ in range(n):
    num.append(int(input()))

num = merge_sort(num)

for i in num:
    print(i)

2) 기본정렬 라이브러리

위에 merge-sort 개념은 이해가는데, 코드를 이해하기가 많이 어려운 것 같습니다. 

이때, 사용할 수 있는게 바로 정렬 라이브러리입니다. 코드도 횔씬 간결해요!

정답코드)

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))
arr.sort()
for i in range(n):
    print(arr[i])

입력을 받아서 배열에 넣은다음, sort()라이브러리를 통해 정렬해준뒤

다시 하나씩 출력하는 방법입니다. 개념도, 코드도 모두 이해하기 쉽네요!

 

병합정렬의 개념은 나중에 기술면접에서도 나올 수 있으니 개념만 짚고 넘어가고,

실전 문제에서는 정렬라이브러리를 사용하는 것이  낫지 않을까 싶네요!

python3으로 자꾸만 시간초과가 뜬다면 pypy3를 사용해서 정답을 제출해보는 요령도 알아두시길 바랍니다!

 

 

도움이 되셨다면 공감과 댓글 그리고 구독을 부탁드립니다.!!