[백준] 수 정렬하기 2(2751) - 파이썬(Python)

🔗 문제 링크

---

https://www.acmicpc.net/problem/2751

 

 

문제 설명

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

입력

- 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

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

출력

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

 

✨ 풀이 과정

---

💡이 문제는 정렬 알고리즘 문제입니다. 주어진 수를 오름차순으로 정렬하는 것이므로 sort 자료형을 쓰면

import sys

n = int(input())
num = []
for _ in range(n):
    num.append(int(sys.stdin.readline()))

num.sort()

for i in num:
    print(i)

이렇게 굉장히 쉽게 해결되는 것을 알 수 있지만, 정렬 부분을 마스터하기 위해 이번에는 자료형을 쓰지 않고 합병정렬을 이용해서 풀어보았습니다.

 

🤔 합병정렬이란?

---

데이터가 저장된 배열을 절반으로 나누고 각각을 순환적으로 정렬해서 정렬된 두개의 배열을 합쳐서 정렬을 하는 것이다. 더 자세하게 로직을 설명하자면,

 

1. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할한다.

2. 정복 : 각각의 작은 문제를 순환적으로 해결한다.

3. 합병 : 작은 문제의 해를 합하여 원래 문제에 대한 해를 구한다.

 

이를 바탕으로 문제를 풀어보았습니다.

 

1. 분할/정복

# 분할정복을 이용한 합병정렬 구현
def sort(arr):
    if len(arr)<2:
        return arr
    
    mid=len(arr)//2
    left=sort(arr[:mid])
    right=sort(arr[mid:])

    return merge(left,right)

분할/정복 부분은 주어진 배열을 반으로 계속 나누다가 길이가 1이 되는 배열까지 나눈다. 길이가 1이 될 때는 다시 arr를 반환하게 되는데 이때의 arr는 길이가 1인 배열로 각각 분할되어 있는 상태이고 분할된 배열 그 자체로 정렬되어 있는 상태이다. 그러므로 그 다음 차례로 반환하는 부분인 return merge(left,right)을 차례대로 레벨 별로 반복하여 수행하면서 순환적으로 왼쪽과 오른쪽 배열을 비교하고 정렬해서 합병해나간다.

 

2. 합병

def merge(left,right):
    new_list=[]
    i=0
    j=0
    
    while (i<len(left)) & (j<len(right)):
        if left[i]>right[j]:
            new_list.append(right[j])
            j+=1
        else:
            new_list.append(left[i])
            i+=1
    while (j<len(right)):
            new_list.append(right[j])
            j+=1
    while (i<len(left)):
            new_list.append(left[i])
            i+=1
    return new_list

분할해서 정렬했던 각각의 왼쪽과 오른쪽 배열을 비교해서 하나로 정렬하는 과정을 반복하는 부분이다.

 

👩‍💻최종 코드

---

# 합병정렬 이용
import sys
input=sys.stdin.readline

n=int(input())
list=[]

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

def sort(arr):
    if len(arr)<2:
        return arr
    
    mid=len(arr)//2
    left=sort(arr[:mid])
    right=sort(arr[mid:])

    return merge(left,right)
    
def merge(left,right):
    new_list=[]
    i=0
    j=0
    
    while (i<len(left)) & (j<len(right)):
        if left[i]>right[j]:
            new_list.append(right[j])
            j+=1
        else:
            new_list.append(left[i])
            i+=1
    while (j<len(right)):
            new_list.append(right[j])
            j+=1
    while (i<len(left)):
            new_list.append(left[i])
            i+=1
    return new_list
    
for i in sort(list):
    print(i)