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

수 정렬하기 2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	163277	44808	30641	30.061%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5
5
4
3
2
1

예제 출력 1

1
2
3
4
5

---

코드

# https://teching.tistory.com/
import sys

# 합병정렬
def mergeSort(nums):
    size = len(nums)
    if size == 1: return nums
    mid = size // 2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    new = [0] * size
    end = l = r = 0
    while len(left) > l and len(right) > r:
        if left[l] > right[r]:
            new[end] = right[r]
            r += 1
            end += 1
        else:
            new[end] = left[l]
            end += 1
            l += 1
    if len(left) > l: new[end:] = left[l:]
    if len(right) > r : new[end:] = right[r:]
    return new


n = int(sys.stdin.readline().rstrip())
nums = [int(sys.stdin.readline().rstrip()) for _ in range(n)]
print(*mergeSort(nums), sep='\n')

해설

그냥 단순하게 파이썬 기본 라이브러리를 사용해도 됐지만 한번 정렬 알고리즘을 만들어보고 싶은 마음에 직접 합 병렬은 만들어 보았다.

합병 정렬 알고리즘을 사용했으며 합병 정렬 알고리즘에 대한 내용은

https://teching.tistory.com/79에서 확인할 수 있다.

정렬 알고리즘 2 : 병합 정렬(합병 정렬, Merge sort)

 

코드 2(파이썬 라이브러리 사용)

#https://teching.tistory.com/
import sys
n = int(sys.stdin.readline().rstrip())
nums = [int(sys.stdin.readline().rstrip()) for _ in range(n)]
print(*sorted(nums), sep="\n")

 

결과 비교

코드1, 코드2순 결과

둘 다 만들어보고 비교해보니 시간이 압도적으로 차이가 난다.. 역시 만들어져 있는 라이브러리를 사용하는 것이 효율적이다... 파이썬에서 사용하는 정렬 알고리즘이 Tim sort인데 이때까지 만들어진 알고리즘들의 장점을 합친 알고리즘이라 그런지 역시 더 빠르고 메모리도 적게 사용한다

물론 내가 구현 능력이 조금 부족하여 불필요하게 시간이 더 들어가는 방법으로 만든 영향도 있지 않을까 싶기도 하다.

왜냐하면 이론상 시간은 팀 정렬이나 합병 정렬이나 O(n*log(n))의 시간이 걸리기 때문이다.