[그리디/heapq] 백준.1715 카드 정렬하기 (python)

이론 정리

- 그리디: 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

   - 핵심이론: 1) 해 선택 2) 적절성 검사 3) 해 검사

 

- 우선순위 큐

• 큐는 FIFO 형식의 자료구조
• 우선순위 큐는 들어오는 순서가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형식의 자료구조
• 일반적으로 힙을 이용하여 구현
• 힙 구현 방법
  • import heapq
  • 빈 리스트 만들어서 갑 넣기
  • heapq 활용 형식
  • !!!힙은 최소가 디폴트 방식이니 최대힙을 구현하기 위해서는 음수 값을 활용
  • 최대힙을 구현할 땐 최대힙, 최소힙 빈 리스트 따로 만들어서 시작
  • min_heap = []
  • max_heap = []   
    • heapq.heappush(리스트 이름, 넣을 요소)
    • heapq.heappop(리스트 이름)

 

문제 링크

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

 

 

문제

나의 풀이

import heapq

N=int(input())
pq=[]
for _ in range(N):
    pq.append(int(input()))


pq.sort()


total=0
while len(pq)>1:
    temp=0
    a=heapq.heappop(pq)
    b=heapq.heappop(pq)
    temp+=a
    temp+=b
    heapq.heappush(pq,temp)
    total+=temp

print(f'{total}')