알고리즘
백준 2751번: 수 정렬2 (python, 파이썬)
블쭌
2020. 10. 27. 21:10
728x90
- 문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
- 입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
- 출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
- 코드
def merge_sort(array):
# 길이가 1이면 끝까지 분할되었기 때문에 종료
if len(array) <= 1:
return array
# 분할
mid = len(array) // 2
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
i, j, k = 0, 0, 0
# 분할된 array 비교
while i < len(left) and j < len(left):
if left[i] < right[j]:
# 오름차순 정렬
array[k] = left[i]
i += 1
else:
array[k] = right[j]
j += 1
k += 1
if i == len(left):
while j < len(right):
array[k] = right[j]
j += 1
k += 1
elif j == len(right):
while i < len(left):
array[k] = left[i]
i += 1
k += 1
return array
n = int(input())
num = []
for _ in range(n):
num.append(int(input()))
num = merge_sort(num)
for i in num:
print(i)
- 출처
728x90