SWEA 1208. Flatten(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh 

SW Expert Academy

 

문제)

 

 

 

 

풀이)

이 문제는 말 그래도 평탄했다.

다만 좀 오래 걸렸던 부분이 있었는데, 그냥 dumpNum 줄여가면서 하나씩 빼면 되는데 괜히 횟수 줄여보겠다고 옆자리 애랑 비교하고 난리났다.

어차피 sort하면 작은 애가 앞으로 올 것이고, 같은애가 여러개 있더라도 더해지면 다시 작은 애가 앞으로 올 것인데 그걸 생각 못했다.

 

어쨌든, 정렬을 통해 오름차순으로 줄세워두고, 맨 뒤에서 하나를 빼 맨 앞으로 넘기는 작업을 반복했다.

그리고, flatten 됨을 확인까지 한다면, 쓸데없이 빼는 작업을 줄일 수 있다!

확인하는 작업은, 정렬 후 맨 앞과 맨 끝의 높이 차이가 0 또는 1인지만 확인하면 된다.

 

//import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Solution_D3_1208_Flatten {

	public static void main(String[] args) throws FileNotFoundException {
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++){
			int dumpNum = sc.nextInt();
			int[] arr = new int[100];
			for(int i=0; i<100; i++) {
				arr[i]=sc.nextInt();
			}
			
			Arrays.sort(arr);
			while(dumpNum>0) {
				if(arr[99]-arr[0]==0 || arr[99]-arr[0]==1)
					break;
				arr[99]-=1;
				arr[0]+=1;
				dumpNum--;
				Arrays.sort(arr);
			}
			int answer = arr[99]-arr[0];
			
			System.out.println("#"+test_case+" "+answer);
		}
		sc.close();
	}

}