[python] 2751. 수 정렬하기 2

• 문제

---

---

 

• 올바른 풀이 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()로 더 간단하게 풀어도 상관없다 !