[SWEA 1208] Flatten JAVA

SWEA 1208 Flatten JAVA

문제

SW Expert Academy

 

입력값

• 가로 길이는 항상 100으로 주어진다.
• 모든 위치에서 상자의 높이는 1이상 100이하로 주어진다.
• 덤프 횟수는 1이상 1000이하로 주어진다.
• 주어진 덤프 횟수 이내에 평탄화가 완료되면 더 이상 덤프를 수행할 수 없으므로 그 때의 최고점과 최저점의 높이 차를 반환한다 (주어진 data에 따라 0 또는 1이 된다).
• 총 10개의 테스트 케이스가 주어지며, 각 테스트 케이스의 첫 번째 줄에는 덤프 횟수가 주어진다. 그리고 다음 줄에 각 상자의 높이값이 주어진다.

834
42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 92 96 43 28 37 92 5 3 54 93 83 22 17 19 96 ...
617
16 40 59 5 31 78 7 74 87 22 46 25 73 71 30 78 74 98 13 87 91 62 37 56 68 56 75 32 53 ...
...

 

출력값

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 최고점과 최저점의 높이 차를 출력한다.

#1 13
#2 32
...

 

알고리즘

PriorityQueue를 활용했습니다. 이 문제의 핵심은 매 dump 시 마다 가장 큰 수에서 1을 빼고, 가장 작은 수에 1을 더하는 것을 어떻게 구현하느냐 입니다. 따라서 PriorityQueue를 2개 선언하여 가장 큰 수와 가장 작은 수가 각 Queue의 맨 위에 올라오도록 구현한 뒤, 매 dump 시 마다 해야 하는 동작을 해주었습니다.

만약 두 Queue의 가장 처음 요소 (peek)가 똑같다면 더 이상 평탄화 작업이 불가하다고 판단하여 값을 출력한다.

 

코드

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

public class Solution {
    public static final int WIDTH = 100;
    public static final int TC = 10;

    public static List<Integer> boxes;
    public static PriorityQueue<Integer> minBoxes;
    public static PriorityQueue<Integer> maxBoxes;
    public static int dump;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for (int tc = 0; tc < TC; tc++) {
            boxes = new LinkedList<>();
            dump = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < WIDTH; i++) {
                boxes.add(Integer.parseInt(st.nextToken()));
            }

            minBoxes = new PriorityQueue<>();
            maxBoxes = new PriorityQueue<>(Collections.reverseOrder());

            minBoxes.addAll(boxes);
            maxBoxes.addAll(boxes);

            for (int i = 0; i < dump; i++) {
                minBoxes.add(minBoxes.poll() + 1);
                maxBoxes.add(maxBoxes.poll() - 1);
                if (minBoxes.peek() == maxBoxes.peek()) {
                    break;
                }
            }            
            System.out.format("#%d %d\n", tc + 1, maxBoxes.poll() - minBoxes.poll());
        }
    }
}