1715-백준-카드 정렬하기

1. 문제 출처

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

1715번: 카드 정렬하기

2. 풀이

가장 작은 두 카드 묶음 값을 더하는 것이 최적의 해이다.

일단은 다음과 같이 구현하였다. 하지만 시간 초과이다...

그래서 heap자료구조를 사용하여 시간을 줄였다...

#입력
n = int(input())

cards = []
for _ in range(n):
    cards.append(int(input()))
# 정렬
cards.sort()


total_count = 0
# card 묶음의 수가 1이 아닐 때 까지 반복
while len(cards) != 1:
    # 제일 작은 카드 묶음 합치기
    united_card = cards.pop(0) + cards.pop(0)
    # 카드 다시 리스트에 넣기
    if cards:
        for idx in range(len(cards)):
            if united_card<cards[idx]:
                cards.insert(idx,united_card)
                break
            if idx == (len(cards)-1):
                cards.append(united_card)
    else:
        cards.append(united_card)
    # 카드 비교 수 최신화
    total_count += united_card
    
    
print(total_count)

Heap구조 사용 시 코드도 간편해지고 경과 시간도 짧아졌다.

# 힙 라이브러리 불러오기 
import heapq
# 압력
n = int(input())

card_heap = []
for _ in range(n):
    temp = int(input())
    heapq.heappush(card_heap , temp)
    
result = 0
# 만약 힙에 데이터가 하나가 아닌 경우
while len(card_heap) !=  1:
    # 제일 작은 값을 2개 빼주고 합쳐준다.
    united_card =  heapq.heappop(card_heap)+ heapq.heappop(card_heap)
    # 결과에 더한다.
    result += united_card
    # 합친값을 heap에 추가한다.
    heapq.heappush(card_heap , united_card)
    
    
    
print(result)