python

BOJ 1715. 카드 정렬하기 (Priority Queue)

륵기 2022. 9. 30. 23:55
728x90
반응형

https://www.acmicpc.net/problem/1715

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

카드의 개수가 최소인 것끼리 더해나가는 것이 가장 최적의 해를 구할 수 있는 방법이다.

우선순위 큐를 사용하여 차례대로 뽑는 방식을 사용

 

문제의 예시로는 카드가 순서대로 10, 20, 40 이렇게 입력된다.

1. 10 + 20

2. (10 + 20) + 40

import queue

card_queue = queue.PriorityQueue()

n = int(input())

for _ in range(n):
    card_num = int(input())
    card_queue.put(card_num)
    
s = 0

while card_queue.qsize() > 1:
    temp1 = card_queue.get()
    temp2 = card_queue.get()

    card_queue.put(temp1+temp2)
    s += (temp1+temp2)
    
print(s)

Queue에 데이터 넣기 : put

Queue에 데이터 뽑기 : get

Queue size : qsize

Queue 비어있는지 확인 : empty

 

 

 

* 임의로 막 넣었을 때 어떤 값이 가장 먼저 뽑히는지 확인

import queue

card_queue = queue.PriorityQueue()

n = int(input())

for _ in range(n):
    card_num = int(input())
    card_queue.put(card_num)
    
print(card_queue.get())

20, 10, 40 순으로 넣었을 때 10이 제일 먼저 뽑히는 것을 확인할 수 있다.

728x90
반응형