[Python] 백준 2751번 : 수 정렬하기 2

Problem

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

Solution

오답 코드1

N = int(input())
numbers = []

for i in range(N) : 
    numbers.append(int(input()))

for i in range(1, len(numbers)) :
    while (i>0) and (numbers[i] < numbers[i-1]) :
        numbers[i], numbers[i-1] = numbers[i-1], numbers[i]
        
        i -= 1
        
for n in numbers : 
    print(n)

오답 코드2

import sys

def bubbleSort(x):
	length = len(x)-1
	for i in range(length):
		for j in range(length-i):
			if x[j] > x[j+1]:
				x[j], x[j+1] = x[j+1], x[j]
	return x

N = int(input())
numbers = []

for i in range(N) : 
    numbers.append(int(sys.stdin.readline()))

bubbleSort(numbers)
        
for _ in numbers :
    sys.stdout.write(str(_)+'\n')

버블정렬을 사용한 풀이로, input과 print를 각각 stdin.readline, write함수로 바꿔주었는데도 시간초과가 나왔다. 버블정렬의 시간복잡도가 O(N²)으로 비효율적이기 때문에 발생한 것으로 보인다.

정답 코드

import sys

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

for i in range(n) : 
    numbers.append(int(sys.stdin.readline()))
        
for j in sorted(numbers): 
    sys.stdout.write(str(j)+'\n')

위 코드는 파이썬의 내장함수인 sorted 함수를 사용하였다. 병합정렬 기반으로 만들어진 함수이기 때문에 최악의 경우에도 시간복잡도 O(N logN)를 갖는다. 또한 입출력은 sys를 import해서 사용했다.

Memo

시간제한이 있는 문제의 경우 파이썬 라이브러리를 활용하면 더욱 효율적이고 빠르게 문제를 풀어낼 수 있는 것 같다.

Ref.

파이썬 내장함수
파이썬 sorted 함수