Q26. 카드 정렬하기
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
카드 장 수가 낮은 순서대로 정렬해야한다.
그리고 제일 작은거 두 개를 꺼내서 더하고 그걸 다시 정렬된 리스트에 넣고..
근데 리스트로 구현하게 되면 제일 작은거 꺼내는건 O(1)이라고 쳐도
다시 넣고 정렬하면 O(N * N log N)이 되므로 다른 방법을 써야한다.
빼고 더하고 넣는 과정이 최대 O(log N)이어야 한다. 그래야 전체적으로 O(N log N)이 되면서 문제를 tle없이 풀수있다.
빼고 넣는게 log N 타임이면서 최소값만을 빼는거.. 뭔지 알겠는가?
min heap을 쓰면 편하게 구현할 수 있다.
import heapq
N = int(input())
data = []
for _ in range(N):
heapq.heappush(data,int(input()))
answer = 0
while len(data) > 1:
n1 = heapq.heappop(data)
n2 = heapq.heappop(data)
answer += n1 + n2
heapq.heappush(data,n1+n2)
print(answer)
이진탐색으로 삽입 위치를 찾아서 삽입하면 되지 않나 라고 생각할 수도 있지만
탐색은 log N이어도 파이썬 리스트는 특정 인덱스에 삽입하는게 평균 O(N)타임이 걸린다.
따라서 heap을 이용하는게 가장 구현도깔끔하고 최적이라 볼 수 있다.