백준 2751번 <수 정렬하기 2>

백준 알고리즘 2751번

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

2751번: 수 정렬하기 2

---

2751번

입력으로 들어오는 숫자를 오름차순으로 정렬하여 출력하면 된다.

 

입력으로 첫 줄에는 수의 개수 N이 주어지고 그 다음 N개의 줄에 수가 주어진다.

 

출력으로는 이 N개의 수를 오름차순으로 정렬하여 출력하면 된다.

---

문제 해결

사실 이 문제는 파이썬에 있는 기본 정렬 라이브러리를 사용하여 풀어도 된다.

그렇지만 정렬에 대해 공부하기 위해 기본 정렬 라이브러리를 사용하지 않았다.

 

수의 크기가 1,000,000이기 때문에 O(N log N)의 시간 복잡도를 가진 정렬 알고리즘을 사용하여야 한다.

 

두 가지 방법으로 문제를 해결하였다.

1) heapq 라이브러리를 사용하여 heap을 이용해 정렬을 수행하였다.

2) merge_sort 함수를 구현하여 사용하였다.

 

1번 방법은 heapq 에 heapq.heappush()를 이용하여 수를 넣고 heapq.heappop()을 이용하여 수를 꺼내면 정렬된 순서대로 나온다.

 

2번 방법은 병합 정렬을 구현하였다. 

병합 정렬은 리스트를 반으로 나눠 left와 right 라는 부분 리스트를 만들고 이를 재귀적으로 병합 정렬을 이용하여 정렬하는 방법이다.

---

코드

import heapq
import sys
input = sys.stdin.readline
n = int(input())
queue = []
array = []
for _ in range(n):
    temp = int(input())
#    heapq.heappush(queue, temp)
    array.append(temp)

#while queue:
 #   print(heapq.heappop(queue))

def merge_sort(array):
    if(len(array) <= 1):
        return array
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    i = 0
    j = 0
    k = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1
    if i == len(left):
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
    return array

temp = merge_sort(array)

for i in temp:
    print(i)

1번 방법을 이용하는 부분은 #을 이용하여 주석처리 하였다.

위에 거가 merge_sort()를 이용한 코드, 아래 거가 heapq를 이용한 코드

---

결과

---