문제
https://www.acmicpc.net/problem/1715
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
priorityQueue.add(Integer.parseInt(bf.readLine()));
}
int result = 0;
while (priorityQueue.size() >= 2) {
int sum = priorityQueue.poll() + priorityQueue.poll();
result += sum;
priorityQueue.add(sum);
}
System.out.println(result);
}
}
풀이 방법
- 우선순위 큐에 카드의 개수들을 넣는다.
- 우선순위 큐를 순회하며 값 두개를 꺼낸 다음 그 둘을 더한다.
- 그 결과를 다시 우선순위 큐에 넣고,
result변수에 더해서 반영한다.
- 이 과정은 큐의 잔여 값이 두개 밑으로 떨어지면 종료한다.
→ 더 이상 연산을 수행할 수 없다.
핵심 포인트
- 이 문제의 경우 일반적인
list를 사용할 경우 메모리 초과가 발생한다.💡주의 사항- 위 문제의 경우 이전의 결과와 연산 이전의 카드 개수를 매번 내림차순으로 정렬해주어야 한다. → 최초에 한번만 수행해준다면 최소값이 나오지 않는다.
- 반례는 다음과 같다.
- 입력 : 1, 2, 2, 2, 2
- 최초 한번만 정렬 : (1+2) + (3+2) + (5+2) = 15
- 매번 정렬 : (1+2) + (2+2) + (3+4) -> 14
- 위 경우와 같이 최초 한번만 정렬한다면 두번째 사이클에서 (3, 2, 2)가 되고, 이는 최소 값을 보장하지 못한다. 최소 값을 보장하기 위해선 (2, 2, 3)이 되어야 한다.
- 하지만
list를 사용하는 경우, 매번 정렬을 수행한다면 메모리 초과가 발생한다.
- 이러한 이유로
우선순위 큐를 사용해야 한다.
보완할 점 / 느낀 점
- 처음 문제를 풀 때, 단순히 그리디라고 생각하고 값 두개를 꺼내서 더하고, 그 값을 다시 넣어서 다음 카드와 더하는 방법으로 구현했다. 하지만 이 경우는 위의 Test 케이스는 통과했지만, 반례가 존재했다.
- 매번 정렬을 하면 메모리 초과가 발생했고, 결국 우선순위 큐에 대해서 찾아보고 풀 수 밖에 없었다.
- 코드 자체는 간단하나, 문제를 보고 우선순위 큐를 사용해야된다는 것을 파악하지 못한다면 풀지 못하는 문제였다.
- 문제를 보고 필요한 자료구조를 파악하는 연습이 필요하며, 추가적으로
PriorityQueue에 대해서도 공부하자.💡기본적으로 숫자에 대해선 낮은 숫자가 우선순위가 높게 책정되어있다. 우선순위는Comparator클래스를 오버라이드 하여 커스텀할 수 있다. 이에 대해서 추후에 연습해보자.
참고자료
- PriorityQueue 설명 : https://kbj96.tistory.com/49