#Algorithm
문제 번호
24173번 알고리즘 수업 - 힙 정렬1(S4)
알고리즘 + 이론
힙 정렬 알고리즘
최소 힙 기반 정렬으로 루트노드에 있는 가장 작은 값을 계속해서 뒤로 보내고 다시 최소 힙 기반 정렬 하면서 내림차순 정렬을 완성
정답 코드
# 24173번
# 5 < N < 500,000
# 1 <= K <= 10**8
# 1 <= A <= 10**9
# 업힙으로 최소 힙 성질을 만족하게 수정
# 그렇게 했으면 가장 끝값과 루트 값을 교환
# 다시 최소 힙 성질에 맞게 수정
# N을 계속 1씩 줄임
# 그러다가 N을 K번 줄였을 때 출력
def build_min_heap(a,n):
for i in range(n//2,0,-1):
heapify(a,i,n)
def heapify(a,k,n):
global cnt,K
left = 2*k
right = 2*k+1
if right <= n:
if a[left-1] < a[right-1]:
smaller = left
else:
smaller = right
elif left <= n:
smaller = left
else:
return
if a[smaller-1] < a[k-1]:
a[k-1],a[smaller-1] = a[smaller-1],a[k-1]
cnt += 1
if cnt == K:
print(a[k-1],a[smaller-1])
return
heapify(a,smaller,n)
N, K = map(int,input().split())
A = list(map(int,input().split()))
cnt = 0
build_min_heap(A,N)
for i in range(N,1,-1):
A[0],A[i-1] = A[i-1],A[0]
cnt += 1
if cnt == K:
print(A[i-1],A[0])
break
heapify(A,1,i-1)
if cnt < K:
print(-1)
느낀점 & 피드백
의사코드가 있어서 편했는데 없이 푸는 것도 연습해봐야할듯
이 글이 도움이 되셨나요?