백준 1715번 카드 정렬하기 파이썬

문제

입력 ,출력

solution

import sys
import heapq
# heapq.heappush(heap, item) : item을 heap에 추가
# heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.

heap = []
n = int(input())
for i in range(n):
    heapq.heappush(heap, int(input()))
cnt = 0
while len(heap) != 1:
    a = heapq.heappop(heap)
    b = heapq.heappop(heap)
    cnt += a + b
    heapq.heappush(heap, a + b)
print(cnt)

설명

우선순위 큐 , 힙을 사용해서 문제를 풀었다.
입력받은값을 최소힙으로 다 넣어주고
heap크기가 1일때까지 pop을 2번 실행해서
그값을 더하고 cnt , 결과값에 저장해주고 그값을 다시 heap에 넣어준다.

후기

우선순위 큐 , 힙을 사용하여 알고리즘은 처음 풀어봤는데
많이 편한것같다..

좋은 웹페이지 즐겨찾기