[백준] Silver 5. 2751 - 수 정렬하기 python

문제 링크

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

---

문제 설명

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

 

입력

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

 

출력

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

---

제출 코드

import sys

input = sys.stdin.readline

n = int(input().rstrip())
result = []

for _ in range(n):
    result.append(int(input().rstrip()))
    
# 입력을 다음과 같이 받을 수도 있다.
result = [int(input().rstrip()) for _ in range(n)]
    
result.sort()
print(*result, sep='\n')

 

풀이

• n번 입력받아 내장함수로 정렬 후 출력한다.
• 내장함수 input()으로 입력받으면 입력이 많을 때 시간초과가 발생할 수 있으므로, sys.stdin.readline을 사용한다.
• readline으로 입력을 받으면 오른쪽에 개행문자가 붙으므로, input().rstrip()으로 제거해준다.

 

알아둘 사항

• 단순 정렬은 최적화된 내장함수 sort(), sorted()를 사용하는 것이 효율적이다.
• 나는 최소힙을 사용해서 풀었는데, 둘 다 시간복잡도는 O(nlogn)이 나오지만 sort() 사용이 더 효율적이다.
• 힙은 입력이 실시간으로 제공되는 경우 최댓값 또는 최솟값을 출력해야 하는 경우에 사용하면 좋다.
• sort() 사용시 메모리는 더 들고 시간은 적게 든다.

import sys
import heapq

input = sys.stdin.readline

n = int(input().rstrip())
heap = []

for _ in range(n):
    heapq.heappush(heap, int(input().rstrip()))

for _ in range(n):
    print(heapq.heappop(heap))