[Algorithm] 1일1솔 - 백준 2751 수 정렬하기2 (python3, PyPy3)

문제링크

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

2751번: 수 정렬하기 2

 

문제설명

O(nlogn) 알고리즘으로 풀어야하는 문제이다.

따라서 시간복잡도가 O(n^2) 인 insertion sort, bubble sort로는 풀기 어렵고, 최악의 시간복잡도가 O(nlogn)인 merge sort나 heap sort로 풀어야 한다.

또한, python 기본 내장함수인 sort, sorted도 병합정렬을 기반으로 만들어진 함수로, O(nlogn)의 시간복잡도를 갖는다.

문제에서 별도의 요구가 없을 때는 직접 함수를 만들어서 사용하는 것보다 내장함수를 사용하는 것이 효율적이므로 우선적으로 sort 함수를 사용해서 풀었다.

처음에는 input() 으로 받았을 때는 시간초과가 났으나, 이후에 sys.stdin.readline() 으로 입력값을 받아 통과하였다.

또한 input() 으로 받는 코드여도 pypy3 로는 통과되었다. (물론, sys.stdin.readline() 코드로도 pypy3로 돌렸을 때 통과된다.)

 

참고

1. sys.stdin.readline 이 input 보다 빠른 이유

input() 내장 함수는 파라미터로 prompt message를 받을 수 있기 때문에 입력받기 전에 prompt message를 출력해야 한다. prompt message가 없는 경우도 있지만, 이 경우 또한 약간의 부하로 작용할 수 있다고 한다. 

반면, sys.stdin.readline() 은 prompt message를 인수로 받지 않는다.

 

또한, input() 함수는 입력받은 값의 개행 문자를 삭제시켜서 리턴(= 입력받은 문자열에 rstrip() 함수 적용시켜 리턴)하기 때문에 느리다. 하지만, sys.stdin.readline() 은 개행 문자를 포함한 값을 리턴하기 때문에 출력에 있어서 귀찮은 면은 있지만, 속도 면에서는 input() 함수보다 빠르다.

 

 

2. pypy3가 python3보다 빠른 이유

pypy3에서는 실행 시, 자주 쓰이는 코드를 캐싱하는 기능이 있기 때문이다. 즉, pypy3 에서는 메모리를 좀 더 사용하여 저장함으로써 실행속도를 개선할 수 있는 것이다.

하지만 pypy3 는 가비지 컬렉터가 python3 와 다른 구조이며 정확한 크기를 할당하는 것이 아니라 대략적으로 크기를 할당하기 때문에 python3 보다 메모리 관리에 신경을 써야 한다.

따라서 코드의 상황에 맞추어서 잘 골라 써야 한다.

 

3. merge sort 알고리즘

merge sort는 divide&conquer를 기반으로 한다.

병합 정렬은 위의 이미지처럼 순서가 뒤죽박죽인 배열을 정렬하기 위해 분할과 정복(Divide & Conquer) 방식을 이용한다.

병합 정렬은 분할 단계에서 분할되는 깊이가 logN에 비례하고, 각 깊이별로 분할이 수행되어 합병해야 하는 배열의 수는 많아지지만, 총 원소의 수는 N개로 같으므로 각 깊이별로 수행되는 merge의 시간복잡도는 O(N) 이다.

 

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

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 재귀함수를 이용해서 끝까지 분할
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    i, j, k = 0, 0, 0

    # 분할된 배열끼리 비교
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    # 먼저 끝났을 때
    if i == len(left):
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
    return arr

print(merge_sort([3,4,1,5,2]))  # [1, 2, 3, 4, 5]

---

문제풀이

1. 파이썬 내장함수 sort 활용

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

tmp.sort()
print(*tmp, sep='\n')

같은 코드여도 PyPy3로 돌렸을 때 훨씬 빠르지만, 메모리를 좀 더 사용하고 있는 것이 확인된다.

 

2. merge sort 알고리즘 활용

위 참고의 merge sort 알고리즘 함수를 이용한다. 입력값은 위 코드와 같이 sys.stdin.readline() 으로 받아야 시간초과가 나지 않는다.

import sys
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    i,j,k = 0,0,0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    if i == len(left):
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
    return arr

n = int(sys.stdin.readline())
tmp = []

for _ in range(n):
	tmp.append(int(sys.stdin.readline()))

tmp = merge_sort(tmp)
print(*tmp, sep='\n')

내장함수 쓰는 것보다 훨씬 시간이 많이 소요된다. 내장함수가 확실히 더 효율적으로 짜여있는 것 같다.

 

---

References

[Python] Input vs. sys.stdin.readline 차이점?

몸소 겪었던 Python과 PyPy의 차이(메모리,속도)

Python3 와 PyPy3 차이

백준 2751 파이썬(정렬)

[백준] 2751 수 정렬하기 2 파이썬 풀이