백준_카드 정렬하기_1715

//알고리즘

1. 우선순위 큐 사용

 -> 카드 뭉치 2개를 꺼내서 더해야 하는데 적은 순서대로 2개를 꺼내서 더하는게 가장 적은 비교회수이기 때문에 우선순위 큐 사용

 -> 예외케이스 : 카드 뭉치가 1개일 경우 비교회수가 0임. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class 카드정렬하기_1715 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int ans = 0;
		PriorityQueue<Integer> q = new PriorityQueue<Integer>();

		int card;
		for (int i = 0; i < n; i++) {
			card = Integer.parseInt(br.readLine());
			q.add(card);
		}
		
		int A,B,sum;
		if(q.size()>1) {
			while (!q.isEmpty()) {
				A = q.poll();
				B = q.poll();
				sum = A+B;
				ans += sum;
				if(q.size()==0) break;
				q.add(sum);
			}
		}
		
		System.out.println(ans);
	}

}

 

※ 우선순위큐를 떠올렸다면 쉽게 풀 수 있는 문제. 예외케이스 때문에 3번이나 실패했음.