[백준 - 1715/ java] 카드정렬하기 - 우선순위 큐

 

필요 알고리즘 개념

 

• 그리디
  • 일정한 규칙을 정해 매번 해당 규칙을 적용하다보면 답이 나오는 알고리즘
• 우선순위 큐
  • 우선순위 큐는 자동으로 수가 우선순위대로 정렬된다. 
  • 우선 순위 큐를 사용해 mini heap을 사용

 

풀이

• 위 문제의 핵심은 연산 과정의 중간 결과가 다시 연산에 사용된다는 것
• 매번 가장 작은 2개를 뽑아 더해주면 된다

 

백준문제의 예시

1. 3개의 수를 받는다.

10 / 20 / 40 

 

2. 연산 시작

10+20 =30

30을 합계에 포함한다. 

중간 연산의 30을 다시 큐에 넣어준다.

30/40

 

3. 두 번째 연산

30+40

70을 합계에 포함한다.

결과 = 100

 

 

코드구현

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

public class QueP1715 {
    static int X;
    static int sum;
    static PriorityQueue<Integer> pq;
    public static void main(String[] args) {


        Scanner sc = new Scanner(System.in);
        X = sc.nextInt();
        pq = new PriorityQueue();

        for (int i = 0; i < X; i++) {
            pq.offer(sc.nextInt());
        }

        while (pq.size() > 1) {
            int tmp =pq.poll()+pq.poll();
            sum += tmp;
            pq.add(tmp);
        }
        System.out.println(sum);

    }
}

 

결과

 

BuffredReader를 사용하여 값을 입력받았을 때 결과

 

확연한 차이가 있음을 알 수 있다. 

입력받는 수가 많을 경우에는 BuffredReader를 사용하자!