백준 1715 : 카드 정렬하기 - python (우선순위 큐, 최소힙)

문제 출처 

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

 

정답 풀이 

되게 흥미로운 문제였다. 

이 문제에서 우선순위 큐를 사용한다? 생각하지 못했고, 

우선순위 큐를 이용하라고 해서 고민해보니, 나온 코드다 ~ 

 

## 1. 초기 설정 

[10,20,30,40,50]이 주어졌다고 생각하자. 

- 아래 그림과 같이 우선순위 큐에다가 주어진 배열의 모든 값을 넣자. 

- answer 변수도 0값으로 할당 

 

## 2.  우선순위 큐에서 작은 값 두개 빼기 

 

- 아래 그림과 같이 우선순위 큐에서 heappop()을 통해 작은 값 두개가 나오도록 한다. 

- heapq의 기본 설정은 최소힙이라 가장 작은 값이 나온다. 

- 그 후, answer에다가 10 + 20을 더한 값을 더해준다 answer = 30

 

 

## 3. 우선순위 큐에 값을 다시 넣기 

 

- 더한 값을 다시 우선순위 큐에 넣는다 

 

## 4.  반복

- 위 과정을 반복하면 된다. 

그런데, 언제까지 ? 가 중요하다. 나는 q의 길이가 0이 되면 반복문이 멈추게 했는데 q의 길이가 1 초과일 때까지만 반복하도록 설정을 해야 한다. 

 

그 이유는 ? 

위의 과정을 계속 반복하다보면, 아래와 같은 그림이 생긴다. 

그리고 맨 마지막엔 초록색 선으로 보이다 시피 

- 270 값 하나만 큐에 들어가있다. 

- 그리고, 큐에 값을 두개는 못빼니까 stop 해줘야 한다. 

 

 

 

 

정답 코드 

import sys
import heapq 
input = sys.stdin.readline
n = int(input())
q = []
for _ in range(n): 
    heapq.heappush(q, int(input()))

answer = 0
while len(q) > 1: 
    num =  heapq.heappop(q) + heapq.heappop(q)
    answer += num 
    heapq.heappush(q, num)

print(answer)