카드 정렬하기
📌문제정렬된 두 묶음의 숫자 카드가 있을 때 각 묶음의 카드의 수를 A,B라고 하면 보통 두 묶음을 합쳐서 하나로 만드는데에는 A+B번의 비교를 해야한다.매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. N개의 숫자 카드 묶음의 각각의 크기가 주어질 때 최소한 몇 번의 비교가 필요한지 구하시오. 📌풀이항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때 최적의 해 보장매 상황에서 가장 작은 크기의 두 카드 묶음을 꺼내어 이를 합친 뒤 다시 리스트에 삽입우선순위 큐 사용(원소를 넣었다 빼는 것만으로 정렬된 결과 얻음) 📌코드import heapqn = int(input())# 힙에 초기 카드 묶음을 모두 삽입h..
코딩테스트
2024. 12. 10. 12:14