백준 1715번: 카드 정렬하기

문제

• https://www.acmicpc.net/problem/1715
• 동적 집합에서 최소값/최대값을 반복적으로 활용할 때 우선순위 큐 활용하기

기록 포인트

• 동적 집합에서 최소값/최대값을 반복적으로 확인해야 할 때 우선순위 큐를 활용하는 방법
  • 매번 전체 정렬을 할 필요 없이 최소값/최대값만 유지해주기 때문에 더 효율적임
• 그 대표적인 사례가 이번 문제임
  • 여러 길이의 정렬된 카드 묶음 중 2개를 골라 하나의 묶음으로 합치는 작업을 반복함
  • 이를 효율화하기 위해 하나의 카드 묶음만 남을 때까지 아래와 같은 절차를 반복함
    • 힙(동적 집합)에서 최소값 2개를 뽑아 합산한 값을 구함
    • 다시 그 값을 힙에 추가
• 오답이 났던 이유는,
  • 최소값 2개를 합한 값이 전체 값들 중에서도 최소값이라고 판단했음
  • 그 결과, 힙에서 하나의 값만 뽑아 이전의 합산 값에 더했음
  • 아래와 같은 반례가 있음
    • 1, 1, 5, 5, 6, 8
      • 1과 1을 더해 2 >> 2, 5, 6, 8
      • 2와 5를 더해 7 >> 7, 5, 6, 8
      • 이 때, 5와 6이 가장 작은 2개의 값이므로 5, 6을 택해 합해야 함
      • 만약 이전의 합산 값을 사용하면 7, 5를 합하게 되므로 오류 발생

접근 방식

• 변화하는 탐색 범위에서(즉, 동적 집합에서) 최소값/최대값을 반복적으로 확인해야 하는 경우, 우선순위 큐를 사용

제출 답안

def parent(i):
    return (i-1)//2
def left(i):
    return i*2+1
def right(i):
    return i*2+2

def heapify(heap, i):
    l, r = left(i), right(i)
    sm = i
    if l < len(heap) and heap[l] < heap[sm]:
        sm = l
    if r < len(heap) and heap[r] < heap[sm]:
        sm = r
    if sm != i:
        heap[sm], heap[i] = heap[i], heap[sm]
        heapify(heap, sm)

def extract(heap):
    L = len(heap)
    if L < 1:
        return False
    min_value = heap[0]
    heap[0] = heap[L-1]
    heap.pop()
    heapify(heap, 0)
    return min_value
    
def insert(heap, v):
    heap.append(v)
    i = len(heap) - 1
    while i > 0:
        p = parent(i)
        if heap[p] <= heap[i]:
            break
        heap[p], heap[i] = heap[i], heap[p]
        i = p

import sys
N = int(sys.stdin.readline())        
        
heap = []
for _ in range(N):
    v = int(sys.stdin.readline())
    insert(heap, v)

total = 0
while len(heap) > 1:
    A, B = extract(heap), extract(heap)
    card = A + B
    total += card
    insert(heap, card)
    
print(total)