[백준] 2751번 수 정렬하기 2 해설 및 풀이 (Python)

백준 수 정렬하기 2

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

---

 

문제

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

입력

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

출력

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

---

 

문제 유형

정렬

 

풀이 방법 도출

1. 수의 개수 N을 입력을 받습니다.
2. for문을 N만큼 반복한 뒤, arr 리스트에 입력 받고 삽입합니다.
3. arr를 오름차순으로 정렬합니다.
4. for문을 arr만큼 반복하여 출력합니다.

 

 

시간 복잡도

• 정렬 : O(N log N)

---

코드 작성

 

import sys

# 빠른 입력
input = sys.stdin.readline

n = int(sys.stdin.readline())
arr = []

# arr 리스트 입력 및 정렬
for _ in range(n):
    arr.append(int(sys.stdin.readline()))
    arr.sort()

# 출력
for num in arr:
    print(num)

 

이렇게 작성한 후, 시간 초과가 일어났다.

정렬을 for문에서 같이 했었던 문제 때문에 시간 초과가 일어난 것으로 보인다.

 

코드 수정(최종 답안)

 

import sys

# 빠른 입력
input = sys.stdin.readline

n = int(input())
arr = []

for _ in range(n):
    arr.append(int(input()))

# 오름차순 정렬
arr.sort()

# 출력
for num in arr:
    print(num)