[백준] 2751. 수 정렬하기2

문제

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

입력

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

출력

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

코드별 제출시간

1218ms

• heapq 모듈 사용
• 최소힙 사용해서 정렬함

import sys
import heapq
input = sys.stdin.readline

n = int(input())
q = list()

for i in range(n):
    heapq.heappush(q, int(input()))

for i in range(n):
    print(heapq.heappop(q))

804ms

• 파이썬 정렬 함수 sort() 사용
• 최소힙보다 더 빠름

import sys
input = sys.stdin.readline

n = int(input())
q = list()

for i in range(n):
    q.append(int(input()))
q.sort()

for i in q:
    print(i)

640ms

• 804ms 코드랑 정렬까지는 코드 동일
• 출력 부분을 for문이 아닌 join으로 바꾸었더니 시간이 많이 줄어듬

import sys
input = sys.stdin.readline

n = int(input())
q = list()

for i in range(n):
    q.append(int(input()))
q.sort()

print('\n'.join(map(str, q)))

내 생각

솔직히 위의 풀이는 좀 바보였다.

heapq 모듈로 정렬하는 방식이 파이썬 내장 sort 함수보다 빠를 거라고 생각했던 내 자신이 약간 부끄러웠다..

파이썬 내장 sort는 무슨 정렬 방식을 사용하길래 왜 이리 빠를까하고 검색해보니 다음 블로그도 나와 같은 의문을 가지고 있었다.

위의 블로그를 보니 Tim이라는 사람이 만든 tim sort를 sort() 메소드에서 사용하고 있고

병합정렬과 삽입정렬을 적절하게 섞어서 시간복잡도가 O(nlogn) 정도라고 한다.

파이썬에서는 sort()를 쓰면 되는데, 자바는 몰라서 공부해봐야겠다.