[BAEKJOON] - 15903번 : 카드합체놀이

15903번 문제 링크

📜 알고리즘 접근 방법

해당 문제는 등급에 비해서 상대적으로 쉽게 생각할 수 있었던 문제였다.

카드 합체 과정은 다음과 같다.
1. x번 카드와 y번 카드를 골라 카드에 적힌 값을 더해준다.(x != y)
2. 계산한 값을 x번 카드와 y번 카드에 덮어 쓴다.

이 후에 전체 카드의 값을 더한 결과값이 최소인 값이 나오도록 알고리즘을 짜면 된다.

최소값이 나오도록 구현하기 위해서는 카드 중 가장 작은 값 2개를 더해주면 된다.

이를 위해, 오름차순 정렬을 활용하여 가장 왼쪽에 있는 값 2개를 더해주도록 구현하면 된다.

⚠️ 주의할 점

카드의 갯수(n)가 1,000 이고, 합체 횟수가 15 * 1,000 = 15,000, a의 값이 1,000,000인 경우 카드 한장에 나올 수 있는 최댓값은 int 타입 이상의 값이 나올 수 있다.

따라서 카드의 수를 담을 배열의 타입을 long 타입으로 선언해주면 된다.

😀 성공

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        int m = Integer.parseInt(st.nextToken());

        long[] a = new long[n];

        st = new StringTokenizer(br.readLine());

        br.close();

        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        for (int i = 0; i < m; i++) {
            Arrays.sort(a);

            long tmp = a[0] + a[1];

            a[0] = tmp;

            a[1] = tmp;
        }
        long sum = 0;

        for (int i = 0; i < a.length; i++) {
            sum += a[i];
        }

        System.out.println(sum);
    }
}

😀 Priority Queue를 활용한 방식

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        int m = Integer.parseInt(st.nextToken());

        PriorityQueue<Long> q = new PriorityQueue<>();

        st = new StringTokenizer(br.readLine());

        br.close();

        for (int i = 0; i < n; i++) {
            q.offer(Long.parseLong(st.nextToken()));
        }

        for (int i = 0; i < m; i++) {
            long tmp = q.poll() + q.poll();
            q.offer(tmp);
            q.offer(tmp);
        }
        
        long sum = 0;

        while(!q.isEmpty()){
            sum += q.poll();
        }

        System.out.println(sum);
    }
}

위 방식대로 PriorityQueue의 자료구조로 구현 시 결과가 훨씬 빠르게 나왔다. 이는 PriorityQueue의 자료구조는 내부적으로 이진 트리 구조로 구현되어 있어 offer 연산과 poll 연산이 모두 O(logN)의 시간 복잡도를 가진다.

일반적으로 Arrays.sort()는 O(NlogN)의 시간복잡도를 가지기 때문에, PriorityQueue를 사용했을 때 훨씬 빠른 결과가 출력될 수 있었던 것이다.