[2751번] 수 정렬하기2

백준 2751번 수 정렬하기2

문제

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

입력

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

출력

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

예제 입력 1

5
5
4
3
2
1

예제 출력 1

1
2
3
4
5

코드 풀이(pypy3 제출)

힙 직접 구현

def heapify(num, idx, n):   # idx : 현재 노드
    left = idx * 2   # 현재 노드 아래 왼쪽 노드
    right = idx * 2 + 1   # 현재 노드 아래 오른쪽 노드
    if left > n:   # 트리에 자식 노드가 없다면 함수 실행 x
        return
    temp_idx = idx
    if left <= n and num[temp_idx] > num[left]:
        temp_idx = left
    if right <= n and num[temp_idx] > num[right]:
        temp_idx = right
    if temp_idx != idx:
        num[idx], num[temp_idx] = num[temp_idx], num[idx]
        heapify(num, temp_idx, n)


def heap_sort(num, n):
    num = [0] + num
    # min heap 구하기
    for i in range(n, 0, -1):
        heapify(num, i, n)

    # heap 정렬 출력하기
    for i in range(n):
        print(num[1])
        num[1], num[n-i] = num[n-i], num[1]
        heapify(num, 1, n-i-1)


n = int(input())
num = [int(input()) for _ in range(n)]

heap_sort(num, n)

힙 모듈 이용

# 힙 자료구조 모듈 임포트
import heapq

heap = []

n = int(input())
# min heap 구하기
for _ in range(n):
    heapq.heappush(heap, int(input()))
# print(heap) : [1, 2, 4, 5, 3]

# 힙에서 원소 하나씩 삭제
for _ in range(n):
    print(heapq.heappop(heap))

내장 함수 이용

n = int(input())
num = [int(input()) for _ in range(n)]

num.sort()

for i in num:
    print(i)

참고 사이트:

• 힙 자료구조 직접 구현
• 힙 모듈 이용