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

🔈 문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.
매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.
N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

 

📝입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

 

📑출력

첫째 줄에 최소 비교 횟수를 출력한다.

 

📚 문제 해석

비교 횟수를 최소로 만들려면 작은 값들을 먼저 비교하고 큰 값들을 나중에 비교해야 한다. 즉 정렬된 데이터를 비교해야만 최소 비교 횟수를 구할 수 있다. 

그렇다면 데이터를 전부 입력 받은 다음 한번만 정렬하고, 데이터 비교를 시작하면 될까?

답은 NO! 이다.

아래 예시를 살펴보자.

정렬된 데이터 20, 30, 40, 45 가 있다.

20 + 30 => 50

50 + 40 => 90

90 + 45 => 135

총 비교 횟수는 50 + 90 + 135 = 275 번이다.

 

위 식을 보면 가장 작은 데이터들을 먼저 비교한다고 하였는데, 40 + 45를 먼저 비교한 것이 아니라 한번 비교한 연산값인 50 + 40을 먼저 비교하게 되었다.

이렇게 제일 처음 한번만 정렬하고 데이터 더하기 시작하면 중간에 연산값은 정렬되지 않은 상태에서 더해지기 때문에 값을 유추할 수가 없다. 그렇다고 한번 할 때마다 정렬을 해주게 된다면 시간초과가 날 것이다.

 

그래서 해당 문제는 !!!우선순위 큐!!!를 사용해서 풀어야 한다. 우선순위 큐는 로그시간대의 시간복잡도로 데이터의 삽입삭제가 가능하기 때문에 시간초과 판정을 받지 않는다. 그리고 최소힙 기반인 자료구조이기 때문에 따로 정렬해줄 필요가 없다.

 

💻 코드

import heaqp
n = int(input())

card = list(int(input()) for _ in range(n)) # 데이터 입력받음 
heapq.heapify(card) # 리스트를 힙구조로 바꿔주는 함수
ans = 0

while len(card) != 1: # n=1라면 ans = 0임 비교가 필요없다.
	first = heapq.heappop(card)
    second = heapq.heappop(card)
    res = first + second # 가장 작은거 두개 꺼내서 더한 다음
    ans += res 
    heapq.heappush(card, res) # 다시 넣음

print(ans)

 

🔗 문제링크 카드 정렬하기

1715번: 카드 정렬하기

 

 

카드