1715-카드 정렬하기

<문제>

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

1715번: 카드 정렬하기

<풀이>

힙큐( heapq)를 사용하면 쉽게 풀수 있는 문제다.

비교횟수를 최소로 하기 위해선 가장 작은 크기의 카드 묶음부터 비교해 나가야 한다.힙큐를 사용하면 우선순위 큐 기능을 구현할 수 있기 때문에 손쉽게 작은 묶음부터 비교해 나갈수 있다.(※참고 : https://hae-sooo97.tistory.com/22?category=925334)

-파이썬-

 

#입력받은 카드 묶음을 순서대로 힙에 삽입
import sys
import heapq
n = int(input())
h = []
answer = 0
for _ in range(n):
    heapq.heappush(h,int(sys.stdin.readline()))
if len(h) == 1:
    print(0)
else:
    while len(h)>1:
        a = heapq.heappop(h)
        b = heapq.heappop(h)
        answer+=a+b
        heapq.heappush(h,a+b)
    
    print(answer)

반복횟수	1	2
a	10	30
b	20	40
answer	30	100
h	[40,30]	[70]

※주의 : while len(h)!=0으로 하면 안된다.(처음풀때 단순히 생각해 while문을 잘못 설정함)

while len(h)!=0과 같이 설정할경우 다음과 같은 일이 벌어진다.

반복횟수	1	2	3
a	10	30	70
b	20	40	index error
answer	30	100
h	[40,30]	[70]

-자바-

package 백준_java;
import java.util.*;
public class Q_1715 {
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        PriorityQueue<Long> pq = new PriorityQueue<Long>();

        for(int i = 0;i<n;i++){
            pq.add(sc.nextLong());
        }

        long num = 0;
        if(pq.size()==1) System.out.print(0);

        else{
            while (pq.size()>1){
                long temp1 = pq.poll();
                long temp2 = pq.poll();
    
                num+= temp1+temp2;
                pq.add(temp1+temp2);
            }
            System.out.print(num);    
        }
        
    }

}