반응형
문제
https://www.acmicpc.net/problem/11279
앞서 힙정렬을 구현할때 사용하였으므로 따로 설명을 붙이지는 않겠다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | import sys input=sys.stdin.readline pq=[] pqlen=0#길이 N=int(input()) while N>0: N-=1 x=int(input()) if x>0:#push pq.append(x) #제일끝에 추가해준다 pqlen += 1 a=pqlen-1 while a>0:#힙구조 만들기 if pq[a]>pq[(a-1)//2]: #부모보다 크다면 바꾸어준다 끝까지 도달하거나 바꿀필요가 없을때까지 pq[a],pq[(a-1)//2]=pq[(a-1)//2],pq[a] a=(a-1)//2 else: break elif x==0:#pop if pqlen==0: print(0) else: print(pq[0]) pq[0]=pq[pqlen-1] pq.pop() pqlen-=1 a=0 #루트노드부터 출발 child=1 while child<=pqlen-1:#힙구조 만들기 길이를 초과하지 않을때까지 if a*2+2<=pqlen-1 and pq[a*2+1]<pq[a*2+2]:#큰자식찾기 child=a*2+2 if pq[child]>pq[a]:#자식이 더크다면 스왑 pq[child],pq[a]=pq[a],pq[child] a=child child=a*2+1 else:#더이상 스왑할 필요없으면 멈춤 break | cs |
반응형
'알고리즘(python) > 자료구조' 카테고리의 다른 글
[Python]우선순위큐 백준 11286 (0) | 2020.02.02 |
---|---|
[Python]우선순위큐 백준 1927 (0) | 2020.02.02 |
[Python]Deque 백준 5430 (0) | 2020.01.18 |
[Python]Deque 백준 1021 (0) | 2020.01.17 |
[Python]Deque 백준 10866 (0) | 2020.01.17 |
최근댓글