Baekjoon 문제 풀기 (2751번 : 수 정렬하기 2) Python

2751번 : 수 정렬하기 2

1. 문제읽기

---

백만의 입력값이 주어졌을 때, 시간초과가 나지 않는 정렬 코드 구현하기

시간 복잡도가 중요한 문제라는 것을 예상했다.
파이썬 기본 정렬은 시간복잡도가 nlogn으로 그냥 내장 정렬 라이브러리를 사용했다.

2. 제출 코드

---

input 대신 sys.stdin.readline으로 구현하고,
복사한 리스트를 리턴하는 sorted 대신 sort로 조금이나마 시간을 빠르게 하려고 노력했다.
결과는 채점이 무지하게 오래걸렸지만 성공하긴 했다.

import sys

n = int(sys.stdin.readline().rstrip())
arr = []
for _ in range(n):
    arr.append(int(sys.stdin.readline().rstrip()))

arr.sort()
for i in arr:
    print(i)

3. 공부할 것

---

기본 내장 라이브러리를 쓰지 않고 시간복잡도가 nlogn인 다른 정렬 알고리즘(힙 정렬, 병합정렬)을 정리해볼까 생각했지만 문제를 풀다보면 저런 정렬을 써야만 하는 문제가 나오지 않을까 하며 그냥 패스한다.