문제

---

코드

---

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

class Solution {
	public static void main(String args[]) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		for (int t = 0; t < 10; t++) {
			int dumpCount = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			PriorityQueue<Integer> minHeap = new PriorityQueue<>();
			PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

			while (st.hasMoreTokens()) {
				int value = Integer.parseInt(st.nextToken());
				minHeap.add(value);
				maxHeap.add(value);
			}

			while (dumpCount-- > 0) {
				minHeap.add(minHeap.poll() + 1);
				maxHeap.add(maxHeap.poll() - 1);
			}

			int ret = maxHeap.poll() - minHeap.poll();
			sb.append(String.format("#%d %d\n", t + 1, ret));
		}
		System.out.println(sb);
	}
}

문제 이해

---

• 평탄화 문제이다.
• 평탄화 작업이란 가장 높은 높이의 블록을 빼서 가장 낮은 높이의 블록에 주는 것이다.
• 입력으로 들어오는 여러 값들에 대해서 dumpCount만큼 평탄화 작업을 수행한 후에 가장 높은 높이와 가장 낮은 높이의 차이를 출력하면 된다.

풀이 방법

---

• 입력을 받으면서 바로 최대힙과 최소힙에 각각 넣는다.
• 힙에 모두 삽입하고 나서 dumpCount만큼 작업을 수행한다.
• 작업은 최대힙과 최소힙에서 각각 한개씩 꺼낸후 최대힙은 1빼고 넣고, 최소힙은 1더하고 넣으면 된다.
• 작업을 마친 후에 최대힙의 값과 최소힙의 값을 뺀 값을 출력한다.

핵심 포인트

---

• 두 개의 힙을 관리하여 최대값과 최소값을 따로 관리한다.

보완할 점 / 느낀 점

---

• 이 문제의 경우 크게 어려운 점은 없었다.
• 오히려 너무 쉽게 풀려서 이상했는데, 예를 들어서 모든 블록의 차이가 0이 될때와 같은 경우에 대한 고려를 하지 않아도 문제가 풀렸다.
• 아이디어와 구현 자체는 어려운 문제가 아니기 때문에 바로 넘어간다.

참고자료

---