[백준 - 1715] 카드 정렬하기

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

문제 분석

먼저 선택된 카드 묶음 -> 비교 횟수의 큰 영향을 끼침

=> 카드 묶음의 카드 개수가 작은 순서대로 먼저 합치기 -> 전체 비교 횟수 감소

 

1. 가장 작은 카드 개수를 가진 묶음 2개를 뽑기
2. 뽑은 2개를 기준으로 합친 새로운 카드 묶음을 다시 넣고 정렬하기

=> 데이터의 삽입 삭제, 정렬이 자주 일어남 -> 우선순위 큐 사용

 

 

PriorityQueue

 

기본적으로 오름차순 정렬을 유지

-> 내부적으로 최소 힙(min-heap)으로 구현 ->가장 작은 요소가 항상 큐의 앞에 온다

• poll() or remove() : 힙의 맨 위에 있는 루트 노드를 제거. (루트 노드는 항상 최소값을 유지)

poll과 remove의 차이

• poll: 우선순위 큐의 요소를 순차적으로 처리할 때 
• remove: 우선순위 큐에서 특정 요소를 직접 제거할 때 

import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        // 입력 받아 저장
        int n = sc.nextInt();

        //우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        //큐에 저장
        for(int i = 0; i < n; i++){
            pq.add(sc.nextInt());
        }
        
        int su1 = 0;
        int su2 = 0;
        int hap = 0;

        //큐에 사이즈가 1이면 종료
        while(pq.size() > 1){
            //오름차순으로 넣었으니 가장 작은 두개의 값 꺼내기
            su1 = pq.poll();
            su2 = pq.poll();
            
            //비교 횟수 결과값에 저장
            hap += su1 + su2;
            
            //더한 값을 큐에 넣고 다시 계산
            pq.add(su1 + su2);
        }
        
        System.out.println(hap);
    }
}