[백준] 1715번 : 카드 정렬하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1715번: 카드 정렬하기

 

1. 문제 설명

2. 풀이과정

문제를 잘 생각해 보면 먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미치는 것을 알 수 있다.

따라서 카드 묶음의 카드 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법이다.

두 개의 카드 묶음을 하나의 카드 묶음으로 합치는 것이므로 현재 카드 묶음의 카드 개수 중 가장 작은 두 카드 묶음을 선택하여 하나의 카드 묶음으로 합치고 이를 다시 현재 카드 묶음들에 포함시킨다.

위 기준으로 새로운 카드 묶음을 다시 정렬하여 과정을 반복한다.

즉, 데이터의 삽입, 삭제, 정렬이 자주 일어나므로 우선순위 큐를 이용하는 것이 편리하다.

 

각 카드 묶음의 카드 개수를 우선순위 큐에 저장한다.

이후 가장 작은 묶음 2개를 선택하여 전체 카드 묶음에서 제거하고 하나로 합친다.

합친 카드 묶음을 다시 전체 카드 묶음 속에 넣는다.

카드 묶음이 최종 하나가 될 때까지 해당 과정을 반복한다.

 

슈도코드

1. N(카드 묶음 개수) 입력받기
2. queue(우선순위 큐)
3. for N만큼 반복: 우선순위 큐에 카드 묶음의 카드 개수 입력받아 저장
4. result(결과 = 0 초기화)
5. while (우선순위 큐 안의 데이터 개수가 1이 될 때까지):
   1. 2개의 카드 묶음을 큐에서 뽑음 (카드 개수가 작은 묶음부터 차례대로)
   2. 2개의 카드 묶음을 하나로 합치는데 필요한 비교 횟수를 결과에 누적으로 더함\
   3. 2개의 카드 묶음을 하나로 합친 결과를 우선순위 큐에 다시 넣음
6. 결과 출력

반응형

3. 소스코드

import sys
from queue import PriorityQueue

N = int(sys.stdin.readline())

queue = PriorityQueue()
for _ in range(N):
    queue.put(int(sys.stdin.readline()))

result = 0
while (queue.qsize() > 1):
    data1 = queue.get()
    data2 = queue.get()

    result += data1 + data2
    queue.put(data1 + data2)

print(result)