[PS] 백준 - 수 정렬하기 2

 

 

입력된 갯수만큼 수를 입력하고,해당 수열을 오름차순으로 정렬해야하는 문제이다.

 

 

<첫번째 시도>

a  = int(input())
entries=[]

for x in range(0,a):
    entries.extend([int(input())])

entries.sort()

for x in entries:
    print(x)

멍청하게도, 그냥 아싸리 파이썬의 정렬함수를 이용하여 제출했으나

결과는

 

 

제한 시간 2초를 넘겨 통과하지 못했다.

 

제한 시간이 2초밖에 안되는 만큼, 가장 빠른 정렬을 이용할 필요가 있다고 생각했고,

퀵 정렬을 이용하기로 하였다.

 

<두번째 시도>

def quicksort(entry):
  if len(entry) < 2:
  	return entry
  elif len(entry) == 2:
    if entry[0]>entry[1]:
      temp = entry[0]
      entry[0] = entry[1]
      entry[1] = temp
  else:
    pivot = entry[0]
    istart = 1
    jstart = len(entry)
		
    while(istart<jstart):
      for i in range(istart,len(entry)):
	      if entry[i] >pivot:
		      istart = i
		      break;
      for j in reversed(range(entry[1],jstart)):
	      if entry[j] <pivot:
		      jstart = j
		      break;
		
      temp = entry[istart]
      entry[istart] = entry[jstart]
      entry[jstart] = temp
			
      istart +=1
      jstart -=1
		
    temp = entry[pivot]
    entry[pivot] = entry[jstart+1]
    entry[jstart+1] = temp
		
    return quicksort(entry[:pivot])+[entry[pivot]]+quicksort(entry[pivot+1:])

entries = list(map(int,input().split()))
print(quicksort(entries))

이래저래 노력하여 퀵 정렬을 짜보았으나 역시 결과는 실패.

 

<세 번째 시도>

def quicksort(array):
	if len(array)>2:
		pivot = array[0]
		i = 1
		j = len(array)-1
		while j>i: 
					
			if array[i]<pivot:
				i+=1
			if pivot<array[j]:
				j-=1
			
			if array[i]>pivot and pivot > array[j]:
				temp = array[i]
				array[i] = array[j]
				array[j] = temp
				i+=1
				j-=1
		
		if array[j]<pivot:
			temp = array[j]
			array[j] = pivot
			array[0] = temp
	
		piv = [pivot]
		result = piv
		if j >1:
			left = quicksort(array[0:j])
			result =left+piv
		if j<len(array)-1:
			right=quicksort(array[j:])
			result+=right
		return result
		
		
	elif len(array)==2:
		if array[0]>array[1]:
			temp =array[0]
			array[0] = array[1]
			array[1] = temp
		return array
	else:
		return array
 



num = int(input())
entries = []
for i in range(0,num):
	entries.extend([int(input())])
	
entries = quicksort(entries)
for n in entries:
	print(str(n))

 

노트북 앞에 앉아서 할 시간이 없어 아이패드로 코딩하였다.

직접 테스트 해 본 결과 제대로 정렬되었다.

 

 

이번엔 틀린 것이 아니라 시간 초과...!

문제는 맞았으나 시간이 너무 오래걸렸다는 뜻.

이제 알고리즘을 좀 더 효율적으로 고쳐보고자 한다.

퀵 정렬의 경우 최악의 경우 n제곱의 시간복잡도를 가진다고 하기에
다음 전략으로 최악의 경우에도 n log n의 시간복잡도를 보장하는 병합정렬을 사용해보기로 했다.

import time
import math

def mergesort(entries):
if isinstance(entries,list) and len(entries) > 1 :
pivot = math.floor(len(entries)/2)-1
first = mergesort(entries[:pivot+1])
second = mergesort(entries[pivot+1:])
return merge(first,second)
else:
return entries

def merge(first,second):
unit=[]

if not isinstance(first,list):
first = [first]
if not isinstance(second,list):
second = [second]

first_p = second_p = 0

while first_p <len(first) and second_p <len(second):
if first[first_p]<second[second_p]:
unit.extend([first[first_p]])
first_p+=1
else:
unit.extend([second[second_p]])
second_p+=1

if first_p>=len(first) and second_p<len(second):
unit.extend(second[second_p:])
else:
unit.extend(first[first_p:])

return unit



num = int(input())
entries = []
for i in range(0,num):
entries.extend([int(input())])

start = time.time()
entries = mergesort(entries)
for n in entries:
print(str(n))
print(time.time()-start)

다음 소스를 제출해보니 역시나 시간초과.
이유가 짐작가지 않아 질문글을 검색해보니 파이썬은 원체 느린 언어라 시간초과가 될 수 있다는 글이 있어서
동일한 코드를 PyPy3로 바꿔서 제출해보았다.

결과는 성공!
파이썬이 느린 언어라는 걸 처음 깨달은 문제였다.