1208. [S/W 문제해결 기본] 1일차 - Flatten [D3] by Java

SW Expert Academy

 

문제와 관련된 내용은 위의 링크에서 확인할 수 있습니다.

---

 

 

 

나의 풀이

이 문제를 해결하기 위해서는 각 덤프에서 가장 높은 박스와 가장 늦은 박스를 찾아야 합니다.

 

문제에 접근할 때에는 시간을 생각하지 않고 브루트포스하게 찾는 방식으로 진행했습니다.

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

class Solution
{
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
		for(int test_case = 1; test_case <= 10; test_case++)
		{
			int dump = Integer.parseInt(br.readLine());
			
			int[] boxes = new int[100];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i = 0; i < 100; i++) {
				boxes[i] = Integer.parseInt(st.nextToken()); 
			}
			
			for(int k = 0; k < dump; k++) {
				int minIndex = 0;
				int minValue = 100;
				int maxIndex = 0;
				int maxValue = 1;
				
				for(int i = 0; i < 100; i++) {
					if (boxes[i] < minValue) {
						minValue = boxes[i];
						minIndex = i;
					}
					
					if (boxes[i] > maxValue) {
						maxValue = boxes[i];
						maxIndex = i;
					}
				}
				
				if (maxValue - minValue <= 1) break;
				
				boxes[minIndex] = boxes[minIndex] + 1;
				boxes[maxIndex] = boxes[maxIndex] - 1;
			}
			
			int heightDifference = Arrays.stream(boxes).max().getAsInt() - Arrays.stream(boxes).min().getAsInt();
			System.out.println("#" + test_case + " " + heightDifference);
		}
	}
}

 

 

그렇기에 시간을 줄일 수 있는 방법을 찾아야 합니다. 가장 핵심인 가장 높은 박스와 낮은 박스를 찾는 방법은,