정렬 백준 2751번 수 정렬하기 2

백준 알고리즘

2751번 수 정렬하기 2

o(nlogn) 알고리즘 사용 !

문제의 설명을 보면 언어에 내장되어 있는 nlogn의 복잡도를 가지는 알고리즘을 사용하라고 되어 있다.

오답 코드
아래는 시간초과가 뜨는 코드이다.

n=int(input())
lst=[]
for i in range(n):
    x=int(input())
    lst.append(x)
lst=sorted(lst)
for i in range(n):
    print(lst[i])

분명 파이썬 내장 라이브러리를 사용했는데 시간초과가 뜬다.

힙 정렬이나 병합 정렬을 직접 구현해야 하나 의문이 들었지만 다른 방법을 먼저 적용해 본다.

입력과 출력에 들어가는 시간이 꽤 클 것으로 보이기 때문에 입 출력에서 시간을 줄여본다.

import sys
n=int(input())
lst=[]
for i in range(n):
    x=int(sys.stdin.readline())
    lst.append(x)
lst.sort()
for i in range(n):
    print(lst[i])

시간은 엄청 오래걸리지만 일단 통과 된다.

출력도 sys로 시간을 줄여보자.

import sys
n=int(input())
lst=[]
for i in range(n):
    x=int(sys.stdin.readline())
    lst.append(x)
lst.sort()
for i in lst:
    sys.stdout.write(str(i)+'\n')

시간이 줄긴 했는데 얼마나 큰 차이인지 딱히 와닿지는 않는다.

병합 정렬이나 힙 정렬을 직접 구현하면 시간이 더 줄어드는 지 테스트 해 볼 필요성이 있어 보인다!

아래 링크에 작성해주신 분이 정리를 잘 해주셨다.
다음에 직접 정렬 알고리즘을 작성해서 테스트를 해보도록 함.
파이썬 정렬

문제 링크이다.
2751 수 정렬하기 2