🤒🤒너모추워

문제링크

백준 #1715. 카드 정렬하기

풀이방법

문제를 보면 대애충 (값 삽입) -> {(정렬) -> (합치기) -> (합 결과 삽입)} * n 이런 흐름으로 문제를 해결한다는 걸 알 수 있죠. 정렬이 자주 일어나고, 정렬의 결과에서 가장 작은 값 두개를 계속 꺼낸다는 풀이 특징을 고려해 문제를 해결해야겠죠??🤓

후보

#1. 정렬 시 Java의 Collection.sort를 사용하면 안 되나??

#2. 힙 사용

위 그림과 같이 시간복잡도에서 힙이 더 유리해 힙을 사용해 문제를 해결했다. (실제로 힙은 반정렬 상태이기 때문에 우선순위가 높은 몇개를 구하고자 할 때 적합한 자료구조다!!)

코드

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

public class CardSorting {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        while (n-- > 0) {
            priorityQueue.add(sc.nextInt());
        }

        int result = 0;
        if (priorityQueue.size() == 1) result = 0;
        else {
            while (!priorityQueue.isEmpty()) {
                int sumCount = priorityQueue.poll() + priorityQueue.poll();
                result += sumCount;
                if (!priorityQueue.isEmpty()) priorityQueue.add(sumCount);
            }
        }

        System.out.print(result);
    }
}

🔥🔥🔥