백준) 카드 정렬하기_1715

이성준·2022년 9월 16일
0

알고리즘

목록 보기
13/13

개요

백준 1715
제목 : 카드 정렬하기
난이도 골드4
https://www.acmicpc.net/problem/1715

문제풀이

문제에서 카드 두개를 비교하는데 A+B번의 비교를 해야한다고 한다. 그러면 여러개의 카드 뭉치가 있을때에는 예로 들면 A,B,C가 있으면 A와B 비교하고 A와B 합친 카드뭉치랑 C를 비교를해야한다. 그래서 최소한의 비교로 카드 뭉치를 합치려면
한번 비교 할때마다 카드 뭉치 중 제일 작은거 두개 골라서 비교하고 합치고 합친것도 카드 뭉치에 포함해서 제일 작은거 두개 골라서 비교하고 합치고를 하나 남을때까지 반복하면 된다.

코드

public class 카드정렬하기_1715 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int totalCompare = 0;
        int tempCompare = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int i = 0; i < N; i++) queue.add(sc.nextInt());


        while (queue.size() > 1) {
            Integer cardDummy1 = queue.poll();
            Integer cardDummy2 = queue.poll();
            tempCompare = cardDummy1 + cardDummy2;
            queue.add(tempCompare);
            totalCompare += tempCompare;
        }

        System.out.println(totalCompare);

    }
}
  1. 큐에서 제일 작은거 두개빼고 합치고 합친거 큐에 넣기
    1-1. 우선순위 큐라서 빠질때는 제일 작은거 두개가 빠진다.
  2. 비교횟수 더해주기
  3. 한개 남을때까지 반복

0개의 댓글