[백준/Python] 2761번 수 정렬하기 2

1️⃣문제 설명

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

2️⃣입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

3️⃣출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

👩🏻‍💻작성한 코드

1. 병합정렬을 사용한 코드

import sys

input = sys.stdin.readline

def merge_sort(list):
    if len(list) <= 1:
        return list
    mid = len(list)//2

    left = merge_sort(list[:mid])
    right = merge_sort(list[mid:])

    i, j, k = 0, 0, 0
    sort_res = []	# 정렬한 리스트 담을

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sort_res.append(left[i])
            i += 1
        else:
            sort_res.append(right[j])
            j += 1
    sort_res += left[i:]
    sort_res += right[j:]

    return sort_res

n = int(input())	# 입력 받을 수의 개수

num = []	# 입력 받은 n개의 수 저장할 리스트

for i in range(n):
    num.append(int(input()))

num = merge_sort(num)

for i in num:
    print(i)

2. sort() 함수를 사용한 코드

import sys
input = sys.stdin.readline

n = int(input())

num = []

for i in range(n):
    num.append(int(input()))

num.sort()

for i in range(n):
    print(num[i])

💡코드 설명

이 문제는 병합정렬과 sort() 함수를 사용해서 총 2가지 방법으로 풀어봤다. 

 

병합정렬이란?

분할·정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 방식이다.

시간 복잡도는 O(nlogn)이다.

 

병합정렬을 사용한 코드에서 merge_sort() 함수를 설명하면, 재귀함수를 사용해서 배열을 길이가 1보다 작아지기 전까지 반으로 계속 나누어 두개의 배열에 나눠 담은 후, 정렬을 진행한다.

 

인덱스 3개( = i, j, k )를 선언해주고, while문에서 두 배열의 값을 비교했을 때 더 작은 값을 sort_res에 append해주고, 더 작은 값을 가르키고 있던 인덱스의 값을 +1 해준다.