카드 정렬하기(BJ_G3_1715)

1. 문제 링크

 

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

 

---

 

2. 나의 코드

메모리: 25264kb
시간: 364ms
코드 길이: 852B
시간 복잡도 : O(NlogN)
설명
- 이 문제의 핵심은 우선순위큐를 사용하는 것이다.
- 카드를 큐에 넣고 1장이 될 때 까지 합친다.
- 그리고 그 합친 값을 결과값에 더한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class BJ_1715 {
    static int N, result;
    static PriorityQueue<Integer> cards;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cards = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            int card = Integer.parseInt(br.readLine());
            cards.offer(card);
        }
        while (cards.size() > 1) {
            int first = cards.poll();
            int second = cards.poll();
            int sumCard = first + second;
            result += sumCard;
            cards.offer(sumCard);
        }
        System.out.println(result);
    }
}

 

 

---

 

3. 정답 코드

package sort;

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

public class CardSort {
	/**
	 * 백준 1714 카드 정렬하기 (https://www.acmicpc.net/problem/1715)
	 */
	public static void main(String[] args) {
		
		//A+B번 비교
		//고르는 순서에 따라 비교 횟수가 달라짐
		//N max 100000
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		PriorityQueue<Long> pq = new PriorityQueue<Long>();
		
		for (int i=0; i<n; i++) {
			pq.add(sc.nextLong());
		}
		
		long num = 0;
		//우선순위 큐에 2개이상 들어있어야 비교가 가능하다.
		while (pq.size() > 1) {
			long temp1 = pq.poll();
			long temp2 = pq.poll();
			
			num += temp1 + temp2;
			pq.add(temp1 + temp2); //합한 묶음 다시 넣기
		}
		
		System.out.println(num);
		
	}
}

 

---

 

4. 배운 점

- 우선순위 큐는 값을 넣으면 가장 작은 값부터 나오게 된다.

- 만약 우선순위 큐의 내림차순을 하고 싶다면 아래 코드처럼 작성하면 된다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());