Problem Solving/Online Judge
[BOJ] #2751 - 수 정렬하기 2
se0m
2021. 6. 15. 02:56
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
** 문제 유형
- 정렬
** 풀이
- 데이터의 개수는 최대 1,000,000개 -> O(nlogn)의 정렬 알고리즘 이용
- n = 1,000,000 ≒ 2^20 (∵ 2^10 ≒ 1,000)
- nlogn = 1,000,000 * 1og2(2^20) ≒ 20,000,000 (1초당)
- 고급 정렬 알고리즘(퀵, 병합, 힙) 을 이용하여 문제 해결
- 혹은 파이썬의 기본 정렬 라이브러리 이용
- 메모리가 허용된다면, 되도록 python 3 보다 더 빠른 PyPy 3를 선택하여 코드 제출
+) 병합 정렬
- 분할 정복 방식 이용
- 절반씩 합치면서 정렬하면, 전체 리스트가 정렬됨
- 시간 복잡도 O(NlogN)
n = int(input())
data = []
for _ in range(n):
data.append(int(input()))
data.sort() # 파이썬 기본 내장 함수 이용
for x in data:
print(x)