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

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

나의 풀이

public class CardSort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Long> queue = new PriorityQueue<>();

        for(int i = 0; i < N; i++) {
            long num = (long)Integer.parseInt(br.readLine());
            queue.offer(num);
        }

        long result = 0;
        while(queue.size() > 1) {
            long a = queue.poll();
            long b = queue.poll();
            result += (a + b);
            queue.offer(a + b);
        }

        System.out.println(result);
    }
}

• 우선순위 큐를 사용하면 간단하게 풀 수 있는 문제였다.
• 입력받은 값들을 우선순위 큐에 넣어준다.
• 큐에 값이 한 개밖에 없다면 계산을 할 수 없기 때문에 while의 조건을 queue.size() > 1 인 동안으로 잡아주었다.
• 큐에서 값 두 개를 빼서 더한 값을 sum 변수에 더해주고, 다시 값 두개의 합을 큐에 넣어준다. 이 과정을 반복하고 result를 출력해주면 된다.

---

ex) 10 20 40 50
turn1
a + b -> 10 + 20 = 30
sum -> 30
큐에 30을 다시 넣어준다.

turn2
a + b -> 30 + 40 = 70
sum -> 30 + 70 = 100
우선순위 큐이기 때문에 40과 50이 아닌 30과 40이 나온다. 그래서 우선순위 큐를 사용해야 최솟값을 구할 수 있는 것이다.

turn2
a + b -> 50 + 70 = 120
sum -> 30 + 70 + 120 = 220
큐에 120밖에 없으므로 종료

답: 220