[백준-파이썬] 1715: 카드 정렬하기

문제 보러 가기!

내 근황 (TMI..)

꺄~ 싸피 공통 PJT를 잘 마무리하고 돌아왔다 ~~!!
마지막 열흘 정도는 PJT에 집중하느라고 PS를 못하다가 오랜만에 문제를 풀었다 !!
내가 좋아하는 heapq를 이용하면 되는 문제였다.

설명

카드 묶음 여러 개가 있는데, 두 묶음씩 골라서 합쳐나간다. 합칠 때는 그 두 묶음의 개수만큼 비교를 해야 한다. 최소 몇 번의 비교가 필요한가?
-> 적은 것부터 합치는 게 좋다 !!라는 걸 파악하고 heapq를 사용하면 됐다.
비교 개수를 담을 변수인 cnt를 0으로 초기화하고 시작했다.
q에 숫자 카드 묶음 각각의 크기를 넣었다. heapify를 이용해서 q를 우선순위 큐로 만들어줬다.
그리고 q의 크기가 1이 될 때까지, 가장 적은 것 두 개씩을 더해서 다시 heapq에 넣었다. 매번 그 적은 것 두 묶음의 개수를 더한 걸 cnt에 더했다.
=> 최종적으로 cnt를 출력하면 답이다.

코드 👩‍💻

import sys, heapq

input = sys.stdin.readline

N = int(input())
q = list(int(input()) for _ in range(N))

heapq.heapify(q)

cnt = 0

while len(q) > 1:
    a = heapq.heappop(q)
    b = heapq.heappop(q)
    heapq.heappush(q, a + b)
    cnt += (a + b)

print(cnt)