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

문제

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

---

두 카드 묶음을 비교하는데 비교 횟수가 카드 장수의 덧셈으로 되있음. 그것에 유의.

 

힙을 이용하여 문제 해결.

heapq 모듈 추가.

import heapq

 

정수 하나를 입력받음.

입력받은 정수만큼 추가로 정수들 입력(카드 장수).

계산 결과를 저장하기 위한 변수 생성.

n = int(input())
nums = [int(input()) for _ in range(n)]
result = 0

 

힙 성질을 만족시키기 위해 입력받은 정수들을 heapify해줌.

heapq.heapify(nums)

 

 

리스트에 2개 이상의 요소가 존재하는 경우 반복.

- 두 요소를 가져욤(삭제 후 반환).

- 두 요소를 더한 결과를 다시 힙에 저장.

- 두 요소의 합을 변수에 더해줌.

 

예) [10, 20, 30]

=> [30]: 10+20 => [30, 30]  // result = 0 + 10 + 20 = 30

=> []: 30+30 => [60] // result = 30 + 30 + 30 = 90

while len(nums) >= 2:
    n1 = heapq.heappop(nums)
    n2 = heapq.heappop(nums)
    heapq.heappush(nums, n1+n2)
    result += n1 + n2

 

결과 출력.

print(result)

 

전체 코드.

import heapq


n = int(input())
nums = [int(input()) for _ in range(n)]
result = 0

heapq.heapify(nums)

while len(nums) >= 2:
    n1 = heapq.heappop(nums)
    n2 = heapq.heappop(nums)
    heapq.heappush(nums, n1+n2)
    result += n1 + n2
print(result)