[1715, 자바] 백준 - 카드 정렬하기 ( 우선순위 큐 )

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

1715번: 카드 정렬하기

 

우선순위큐에 대한 이해와 그리디 알고리즘을 합친 방식이다.

 

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	PriorityQueue<Integer> queue = new PriorityQueue<>();
	int size = sc.nextInt();
	for(int i=0; i < size; i++) {
		queue.add(sc.nextInt());
	} // 입력 종료
	
	int result =0;
	if(size == 1) {
		System.out.println(0);
	}else {
		
		while(true) {
			if(queue.size()<=2) {
				break;
			}
			int a = queue.poll();
			int b = queue.poll();
			result += a+b;
			queue.add(a+b);
			
		}
		
		int q = queue.size();
		for(int i=0; i < q; i++) {
			result += queue.poll();
		}
		System.out.println(result);
	}
}
}

 

제일 작은 수 끼리 연산을 하고 연산한 값을 다시 우선순위 큐에 넣어주고

 

그다음으로 작은 두 값을 우선순위큐의 크기가 2보다 작거나 같아질 떄 까지 반복을 한다.