[백준 1715번]카드 정렬하기

문제 접근 방법

1. 리스트 정렬
2. 가장 작은 원소 두개 꺼내서 합치고 다시 집어넣기
3. 1, 2번 반복

작성 코드

n = int(input())
count = n

deck = []
for i in range(n):
    deck.append(int(input()))

total = 0
while len(deck) > 1:
    deck.sort(reverse=True)
    a = deck.pop()
    b = deck.pop()
    total += a + b
    deck.append(a + b)

print(total)

5분만에 뚝딱 작성해서 정답 제출했는데 자꾸 시간초과가 뜨는 것이었다.

여기서 뭘... 더 줄일 수 있는게 있나...? 고민하다가 30분 지나서 그냥 답지 봤음.

답지를 봤는데 아니 글쎄 코드는 맞는데 자료구조를 리스트가 아니라 넣기만 해도 자동으로 정렬되는 우선순위 큐로 쓰란다. 이거 안쓰면 통과 안됨.

정답 코드

import heapq

n = int(input())
count = n

deck = []
for i in range(n):
    heapq.heappush(deck, int(input()))

total = 0

while len(deck) > 1:
    a = heapq.heappop(deck)
    b = heapq.heappop(deck)
    sum = a + b
    total += sum
    heapq.heappush(deck, sum)

print(total)

자료구조만 우선순위 큐로 바꿔줬다.