백준 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를 합하게 되므로 오류 발생
- 1, 1, 5, 5, 6, 8
접근 방식
- 변화하는 탐색 범위에서(즉, 동적 집합에서) 최소값/최대값을 반복적으로 확인해야 하는 경우, 우선순위 큐를 사용
제출 답안
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)
Author And Source
이 문제에 관하여(백준 1715번: 카드 정렬하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@johnny/beak-1715저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)