해당 문제는 우선순위 큐(Priority Queue)를 사용하여 효율적으로 해결할 수 있습니다.
파이썬에서 제공하는 heapq 모듈을 사용하여 우선순위 큐를 구현할 수 있습니다.
숫자 카드 묶음의 크기를 우선순위 큐에 넣은 다음,
가장 작은 두 묶음을 꺼내 그 합을 다시 우선순위 큐에 넣는 과정을 반복하면,
전체 비교 횟수를 최소화할 수 있습니다.
의사코드:
함수 최소비교횟수구하기(숫자카드묶음):
우선순위큐 초기화
숫자카드묶음을 순회하면서 각 묶음을 우선순위큐에 추가
총비교횟수 = 0
우선순위큐의 크기가 1보다 클 동안 반복:
가장 작은 묶음 = 우선순위큐에서 제거
두 번째로 작은 묶음 = 우선순위큐에서 제거
현재비교횟수 = 가장 작은 묶음 + 두 번째로 작은 묶음
총비교횟수에 현재비교횟수 추가
합친 묶음 = 가장 작은 묶음 + 두 번째로 작은 묶음
합친 묶음을 우선순위큐에 추가
반환 총비교횟수
의사코드 구성 단계:
1. 우선순위 큐를 초기화하고, 입력 받은 숫자 카드 묶음의 크기들을 우선순위 큐에 추가합니다.
2. 우선순위 큐에서 가장 작은 두 개의 숫자 카드 묶음을 제거합니다.
3. 이 두 묶음을 합치고, 그 합의 크기로 비교 횟수를 계산하여 총 비교 횟수에 더합니다.
4. 합친 묶음을 다시 우선순위 큐에 추가합니다.
5. 우선순위 큐에 하나의 묶음만 남을 때까지 2~4단계를 반복합니다.
6. 총 비교 횟수를 반환합니다.
→ 이 접근 방식은 우선순위 큐를 통해 항상 가장 작은 두 개의 묶음을 합치므로,
최소 비교 횟수로 모든 카드 묶음을 하나로 합칠 수 있습니다.
코드 구현 단계:
1. 중간 부분 : 핵심 알고리즘 구현:
가장 먼저, 숫자 카드 묶음들을 합치는 과정에서 최소 비교 횟수를 계산하는 핵심 알고리즘을 구현합니다.
이 부분에서는 우선순위 큐(최소 힙)을 사용하여 항상 가장 작은 두 카드 묶음을 찾아 합치는 과정을 반복합니다.
import heapq
def min_compare(card_set):
heap = []
for card in card_set:
heap.heappush(heap, card)
total_compare = 0
while len(heap) > 1:
first = heapq.heappop(heap)
second = heapq.heappop(heap)
total_compare += first + second
heapq.heappush(heap, first + second)
return total_compare
→ 이 코드는 주어진 숫자 카드 묶음들을 우선순위 큐에 넣고,
큐에서 가장 작은 두 개의 묶음을 꺼내 그 크기를 합한 다음,
그 합을 다시 큐에 넣는 과정을 모든 카드가 하나의 묶음이 될 때까지 반복합니다.
각 단계에서의 비교 횟수는 합친 묶음의 크기와 같으며,
이를 총 비교 횟수에 누적합니다.
2. 하단 부분 : 결과 출력
→ 핵심 알고리즘 구현 후, 이를 활용하여 주어진 입력에 대한 최소 비교 횟수를 계산하고
결과를 출력하는 부분을 작성합니다.
# 최소 비교 횟수 계산
result = min_compare(card_set)
# 결과 출력
print(result)
3. 상단 부분 : 입력 처리
→ 마지막으로, 사용자로부터 숫자 카드 묶음의 개수와 각 묶음의 크기를 입력받는 부분을 작성합니다.
이 부분은 전체 코드의 시작 부분에 위치합니다.
N = int(input()) # 숫자 카드 묶음의 개수 입력
card_set = [int(input()) for _ in range(N)] # 각 숫자 카드 묶음의 크기 입력
전체 코드 구현
import heapq
def min_compare(card_set):
heap = [] # 들여쓰기를 공백 4개로 통일
for card in card_set:
heapq.heappush(heap, card) # 들여쓰기를 공백 4개로 통일
total_compare = 0
while len(heap) > 1:
first = heapq.heappop(heap)
second = heapq.heappop(heap)
total_compare += first + second
heapq.heappush(heap, first + second)
return total_compare
N = int(input())
card_set = [int(input()) for _ in range(N)]
result = min_compare(card_set)
print(result)
결과:
