[백준 / 골드4] 1715 카드 정렬하기 (Java)

Ilhwanee·2022년 12월 7일
0

코딩테스트

목록 보기
138/155

문제 보기



사용한 것

  • 작은 카드 뭉치부터 뽑기 위한 우선순위 큐


풀이 방법

  • 우선순위 큐를 사용해서 가장 작은 두 카드 뭉치를 뽑는다.
  • 카드 뭉치의 합을 answer에 더한다.
  • 두 카드 뭉치를 합쳐 pq에 다시 넣는다.
  • pq에 하나가 남을 때까지 반복한다.


코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            pq.offer(Integer.parseInt(br.readLine()));
        }

        // 가장 작은 두 수 합쳐서 PQ에 다시 넣기
        int answer = 0;
        while (pq.size() > 1) {
            int num1 = pq.poll();
            int num2 = pq.poll();
            int sum = num1 + num2;
            answer += sum;
            pq.offer(sum);
        }

        System.out.println(answer);
    }
}


profile
블로그 이전 -> https://pppp0722.github.io

0개의 댓글