728x90
반응형
- 문제
- 올바른 풀이 1
import sys
# merge_sort로 해결
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
i, j, k = 0, 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]: # left가 더 작으면 arr[k]는 left
arr[k] = left[i]
i += 1
else: # right가 더 작으면 arr[k]는 right
arr[k] = right[j]
j += 1
k += 1
if i == len(left):
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
elif j == len(right):
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
return arr
N = int(input())
num_list = []
for i in range(N):
num = int(sys.stdin.readline())
num_list.append(num)
num_list = merge_sort(num_list)
print(*num_list, sep='\n')
해당 문제를 merge_sort로 해결하면 다음과 같다.
리스트를 반으로 나누어 투 포인터를 통해 left 처리, right 처리를 해주는 로직이다.
- 올바른 풀이 2 (더 간단한 방법)
# sorted()로 해결
import sys
N = int(input())
num_list = []
for i in range(N):
num = int(sys.stdin.readline())
num_list.append(num)
num_list = sorted(num_list)
print(*num_list, sep='\n')
하지만 해당 문제를 sorted()로 더 간단하게 풀어도 상관없다 !
728x90
'자료구조 및 알고리즘 > 백준' 카테고리의 다른 글
[python] 18870. 좌표 압축 (0) | 2023.01.19 |
---|---|
[python] 1427. 소트인사이드 (0) | 2023.01.18 |
[python] 1181. 단어 정렬 (0) | 2023.01.18 |
[python] 2108. 통계학 (0) | 2023.01.16 |
[python] 11728. 배열 합치기 (0) | 2023.01.16 |