[백준 2751번-파이썬/Python] 수 정렬하기 2

 

http://acmicpc.net/problem/2751

{코드}

import sys
[sys.stdout.write(str(v)+'\n') for v in sorted([int(sys.stdin.readline()) for _ in range(int(sys.stdin.readline()))])]

{설명}

이 문제는 O(nlogn)의 복잡도를 요구하기 때문에 파이썬의 기본 내장 정렬 함수를 사용할 수 있습니다.

다만, 입력 횟수가 많고 숫자의 길이도 짧지 않아 sys 라이브러리의 입출력을 사용하면 Python3로 통과할 수 있습니다.

기본 내장 함수 결과

{코드}

import sys
def input():
	return int(sys.stdin.readline())
def print(v):
	sys.stdout.write(str(v)+'\n')
def mergeSort(x):
	if len(x) > 1:
		mid = len(x)//2
		lx, rx = x[:mid], x[mid:]
		mergeSort(lx)
		mergeSort(rx)
		li, ri, i = 0, 0, 0
		while li < len(lx) and ri < len(rx):
			if lx[li] < rx[ri]:
				x[i] = lx[li]
				li += 1
			else:
				x[i] = rx[ri]
				ri += 1
			i += 1
		x[i:] = lx[li:] if li != len(lx) else rx[ri:]
data = [input() for _ in range(input())]
mergeSort(data)
[print(v) for v in data]

{설명}

병합 정렬을 이용한 코드로 병합 정렬은 배열을 계속해서 2개로 나눈다음 나눠진 배열을 합치며 정렬합니다. (두 정렬된 배열을 합치는데 걸리는 시간 복잡도는 길이가 m, n인 배열 두 개가 있으면 O(m+n)이고 길이가 1인 배열은 정렬된 배열입니다.)

또한, 파이썬은 내장 함수도 원하는대로 바꿀 수 있으나 원래 함수의 기능은 사용할 수 없게 됩니다.

*참고자료: ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html, 코딩하는 거니님의 병합 정렬 영상

 

병합 정렬은 PyPy3로 제출해야한다.

{코드}

 

import heapq
import sys
def input():
	return int(sys.stdin.readline())
def print(v):
	sys.stdout.write(str(v)+'\n')
data = [input() for _ in range(input())]
heapq.heapify(data)
[print(heapq.heappop(data)) for _ in range(len(data))]

{설명}

힙 정렬을 이용한 코드로 주어진 리스트를 힙 자료구조로 만든 다음 루트 노드를 빼며 결론적으로 정렬하는 코드입니다.

*파이썬에서 힙은 heapq를 사용해 쓸 수 있으며 최소 힙만을 지원합니다.

**참고자료: reakwon.tistory.com/42

 

 

* 퀵 정렬이 없는 이유는 기본적인 퀵 정렬 구현 코드는 최악의 경우 O(n^2)의 시간 복잡도를 가지기 때문입니다.