문제사항

골드 4단계 문제였다.

초반에List로 문제를 풀며 예제 입력에 대한 예제 출력이 도출이 되었지만, 수 많은 반례로 틀렸습니다를 반복하였다 😂

찾아보니까 그리디 알고리즘에서 자주 쓰이는 자료구조 형태가 PriorityQueue였고, 이 역시 PriorityQueue를 활용하였다.

그리디 알고리즘

그리디 알고리즘(Greedy Algorithm)은 현재 상황에서 가장 최선의 선택을 하는 방식이다.

전체 문제를 한 번에 해결하는 대신, 그 순간에 가장 좋은 선택을 하며 부분 문제를 해결해 나가는 방식인 것

그리디 알고리즘을 사용할 때 자주 사용되는 자료구조로는 우선순위 큐(Priority Queue) 가 있다.

PriorityQueue 클래스

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(10);
pq.offer(5);
pq.offer(20);

System.out.println(pq.poll()); // 출력: 5
System.out.println(pq.poll()); // 출력: 10
System.out.println(pq.poll()); // 출력: 20

우선순위 큐는 가장 우선순위가 높은 원소부터 꺼낼 수 있는 자료구조

class Person implements Comparable<Person> {
    int age;
    String name;

    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public int compareTo(Person other) {
        return this.age - other.age; // 나이 순으로 정렬
    }
}

PriorityQueue<Person> pq = new PriorityQueue<>();
pq.offer(new Person(30, "Alice"));
pq.offer(new Person(20, "Bob"));
pq.offer(new Person(25, "Charlie"));

System.out.println(pq.poll().name); // 출력: Bob
System.out.println(pq.poll().name); // 출력: Charlie
System.out.println(pq.poll().name); // 출력: Alice

객체를 우선순위 큐에 넣을 때 정렬 기준을 직접 구현도 가능하다.

Comparator 인터페이스를 구현하여 PriorityQueue의 생성자에 전달하였다.

알고리즘 분류

1. 그리디
2. 우선순위 큐

코드

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));
        int n = Integer.parseInt(br.readLine());
        //List<Integer> arr = new ArrayList<>(); List 대신 우선순위 큐(PriorityQueue) 사용
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int answer = 0;

        for (int i = 0; i < n; i++) {
            pq.offer(Integer.parseInt(br.readLine()));
        }

        while (pq.size() > 1) {
            int n1 = pq.poll(); // poll은 꺼낸 후 삭제해버림
            int n2 = pq.poll();
            int sum = n1 + n2;
            answer += sum;
            pq.offer(sum); // 저장, 최종적으론 하나만 남음
        }

        System.out.println(answer);
    }
}