이번 문제는 백준 1715 : 카드 정렬하기 이다.
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
입력으로 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.
출력으로 첫째 줄에 최소 비교 횟수를 출력한다.
카드를 정렬할 때 가장 최소의 비교 횟수를 지니도록 해야 한다. 이는 매 정렬마다 가장 적은 수의 카드 더미 둘을 합치는 방식으로 해결할 수 있다. 그리디 알고리즘을 적용한다면 해당 문제는 쉽게 해결이 가능하다. 매번 정렬할 필요 없이 pop 할 때마다 최소의 값이 나오도록 하기 위해 heap을 사용하였다.
코드는 이러하다.
import heapq
n = int(input())
card = []
for _ in range(n):
heapq.heappush(card, int(input()))
result = 0
while len(card) != 1:
one = heapq.heappop(card)
two = heapq.heappop(card)
temp = one + two
result += temp
heapq.heappush(card, temp)
print(result)
우선 heapq를 임포트 하여 사용할 수 있도록 한다.
n을 입력받은 뒤, card 리스트를 선언하여 heapq로 사용될 수 있도록 한다. 이후 반복문을 이용해 card 큐에 입력받은 값을 삽입한다.
이제 card 리스트에 원소가 하나 남을 때까지 반복문을 실행한다. 반복문 내부는 이러하다. 가장 작은 크기를 갖는 카드 더미 두 개를 꺼낸다. 이들의 합을 결과에 더해 준 뒤, 다시 card 큐에 넣어 더미가 합쳐진 채로 들어가도록 한다.
해당 과정을 마무리하면 최종 결과가 출력되게 된다.
(코드길이: 279 byte(s) / 수행 시간: 4920 ms / 메모리: 31672 kb)
그리디 알고리즘이 크게 어려운 것은 아니나 합쳐진 카드 더미가 기존에 입력받은 카드들보다 더 커질 수 있다는 점과, heap을 생각하지 못한다면 다소 까다롭게 느껴질 수 있는 문제이다. 다양한 알고리즘에 익숙해지도록 하자. 특히 queue를 이용한 풀이가 더 접근하기 쉬운 경우가 많으므로 바로바로 떠올릴 수 있도록 하자.
