자료구조 및 알고리즘/백준

[python] 2751. 수 정렬하기 2

viamemine 2023. 1. 18. 12:50
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