[Python] BOJ/백준 15903번 카드 합체 놀이

[문제]

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

15903번: 카드 합체 놀이

 

[풀이]

처음에는 간단하게 sort 함수를 이용해 풀었는데 이는 O(nlogn)으로 우선순위 큐를 이용하면 O(logn)으로 시간복잡도를 줄일 수 있다.

우선순위 큐 사용시, 값을 바꿀 카드 2개를 우선순위 큐에 삽입만 하면 되기 때문에 매번 정렬해야하는 sort 보다 훨씬 효율적인 것이다.

 

따라서 cards 리스트를 만든 후 heapq 내장 모듈 사용해 힙을 구현했다.

 

 

[힙큐 사용 코드]

import sys
import heapq

n, m = map(int, sys.stdin.readline().split())

cards = []
card_list = list(map(int, sys.stdin.readline().split()))

for card in card_list:
    heapq.heappush(cards, card)
    
for _ in range(m):
    card1 = heapq.heappop(cards)
    card2 = heapq.heappop(cards)

    heapq.heappush(cards, card1 + card2)
    heapq.heappush(cards, card1 + card2)
print(sum(cards))

 

[sort 코드]

import sys

n, m = map(int, sys.stdin.readline().split())
cards = sorted(list(map(int, sys.stdin.readline().split())))
for _ in range(m):
    cards[0] = cards[1] = cards[0] + cards[1]
    cards = sorted(cards)
print(sum(cards))