백준 1715번 : 카드 정렬하기
각각 N장, M장인 카드묶음 A와 B를 합치기 위해선 N+M번의 비교가 필요하다고 한다.
카드 묶음의 개수와 각각의 크기가 주어질 때, 두 묶음씩 골라 서로 합쳐나가면서
하나의 카드묶음으로 만드는데 필요한 최소 비교횟수를 출력해야 한다.
읽자마자 든 생각은 '그냥 작은 것부터 합치면 되는 거 아님?;;' 이였다.
아무리 읽어도 그게 맞는데 solved 골드 4에 배정되어 있길래 당황스러웠다.
(역시 믿을게 못되는 티어표..)
설계
가장 작은 것부터 계속 고르면 되는 문제이니 그리디 문제라고 할 수 있겠다.
입력의 개수가 최대 100,000으로 수상쩍으니 리스트말고 우선순위 큐를 사용하기로 했다.
정정합니다.
우선순위 큐를 사용해야하는 이유는 입력의 크기 때문이 아닙니다.
단순히 오름차순 정렬을 사용하게 되면
합쳐진 값을 리스트에 넣을 때마다 정렬해야 하기 때문입니다.
최소힙을 사용해야 시간초과를 피할 수 있습니다.
문제를 제출하고 찾아보면서 깨달은 것이지만 이 문제는 그리디보단 자료구조 문제에 가깝다.
파이썬의 경우, 힙 모듈을 사용하는 방법만 알면 정말 쉽게 구현할 수 있다.
입력을 모두 최소힙에 넣고, 그 중에서 가장 작은 2개를 꺼낸다.
두 값의 합을 결과값에 더하고 다시 힙에 넣으면 된다.
구현
일단 입력받은 각 카드묶음의 개수를 힙에 삽입한다. 파이썬 heapq모듈은 최소힙을 기본으로 하기 때문에 별도의 조작은 필요없다.
Deck = []
for _ in range(int(input())):
HQ.heappush(Deck,int(input()))
총 비교횟수를 나타낼 변수 result를 선언한다. 초기값은 0.
result = 0이제 힙을 활용해서 작은 값부터 꺼내면서 계산하면 된다.
반복문의 구성은 아래와 같다.
- heappop()을 사용해서 가장 작은 값부터 2개의 카드묶음 A,B를 꺼내고
A,B의 합을 result에 더한다. - 묶은 카드묶음 (A+B)는 다시 힙에 삽입한다.
- 힙에 하나만 남으면 모두 합친 것이니 반복문을 종료한다.
코드로 보면,
while len(Deck) > 1 :
tmp = HQ.heappop(Deck) + HQ.heappop(Deck)
result += tmp
HQ.heappush(Deck,tmp)반복문의 종료 조건만 잘 설정하면 틀릴 일이 없다.
이제 결과를 출력하면 구현 끝이다.
전체코드
import sys
import heapq as HQ
input = sys.stdin.readline
Deck = []
for _ in range(int(input())):
HQ.heappush(Deck,int(input()))
result = 0
while len(Deck) > 1 :
tmp = HQ.heappop(Deck) + HQ.heappop(Deck)
result += tmp
HQ.heappush(Deck,tmp)
print(result)추가로
이 문제는 사실 그리디라기 보단 자료구조 문제에 가깝다. 하지만, 그리디 문제를 해결할 때 올바른 자료구조를 선택하는 것이 중요하다는 것을 말하기 위해서 예제로 선정했다.
실제로 이 문제를 퀵정렬인 sort()로 풀면 시간초과가 발생한다.
