[SWEA] 1208번 Flatten 문제

나름 시간을 줄여서 풀고자 노력했다

 

package D3;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class SW_1208 {  //Flatten 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int dump;   //최대덤프횟수
        for (int t = 1; t <= 10; t++) {
            dump = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] boxes = new int[100]; //각 박스들의 높이별로 저장할 배열
            for (int i = 0; i < 100; i++) {
                boxes[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(boxes);
            int max = 99; int min = 0; int tmp = 0;
            while (boxes[99] - boxes[0] == 1 || dump != 0) {    //가장 높은곳과 가장 낮은곳 차가 1일경우 또는 dump를 다한경우까지
                boxes[99]--;
                boxes[0]++;
                dump--;
                while (boxes[max] < boxes[max-1]) {     //값을 부분정렬해준다
                    tmp = boxes[max];
                    boxes[max] = boxes[max - 1];
                    boxes[max - 1] = tmp;
                    max--;
                }
                max = 99;
                while (boxes[min] > boxes[min+1]) {     //값을 부분정렬해준다
                    tmp = boxes[min];
                    boxes[min] = boxes[min + 1];
                    boxes[min + 1] = tmp;
                    min++;
                }
                min = 0;
            }
            bw.write("#" + t + " " + (boxes[99] - boxes[0]));
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}