SWExpertAcademy 1208번-Flatten(JAVA)

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

SW Expert Academy

 

[제약 사항]

가로 길이는 항상 100으로 주어진다.

모든 위치에서 상자의 높이는 1이상 100이하로 주어진다.

덤프 횟수는 1이상 1000이하로 주어진다.

주어진 덤프 횟수 이내에 평탄화가 완료되면 더 이상 덤프를 수행할 수 없으므로 그 때의 최고점과 최저점의 높이 차를 반환한다 (주어진 data에 따라 0 또는 1이 된다).

[입력]

총 10개의 테스트 케이스가 주어지며, 각 테스트 케이스의 첫 번째 줄에는 덤프 횟수가 주어진다. 그리고 다음 줄에 각 상자의 높이값이 주어진다.

[출력]

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

 

import java.util.Arrays;
import java.util.Scanner;

public class flatten {
	private static int dump(int num, int[] arr) {
		Arrays.sort(arr);
		//종료 조건1: 덤프 횟수 끝나면 최대 높이와 최소높이 차이 return
		//종료 조건2: 덤프 횟수 이내에 평탄화가 완료되면 더이상 덤프 수행x
		if(num == 0|| arr[arr.length-1]-arr[0]<=1) 
			return arr[arr.length-1]-arr[0]; 
		//반복
		arr[arr.length-1]-=1;	//가장 높은 곳 -1
		arr[0]+=1;				//가장 낮은 곳 +1
		Arrays.sort(arr);
		return dump(num-1, arr);//dump횟수 -1하고 다시 부르기
	}
	
	public static void main(String[] args) {	
		Scanner sc = new Scanner(System.in);
		int dump_n;
		int[] arr;
		StringBuilder sb = new StringBuilder();
		//입력부
		for(int i = 0; i < 10; i++) {
			dump_n = sc.nextInt();
			arr = new int[100];
			for(int j = 0; j < 100; j++) {
				arr[j] = sc.nextInt();
			}
			sb.append("#"+(i+1)+" "+dump(dump_n, arr)+"\n");
		}
		
		//출력부
		System.out.println(sb);
	}
}

 

재귀함수를 이용해 상자의 높이를 평탄화하였습니다.

 

*dump(int num int[][] arr) 

-매개변수

int num = 수행가능한 dump 횟수

int[][] arr = dump를 실행할 대상 배열

 

-종료조건

⑴ 종료 조건: 덤프 횟수 끝나면 최대 높이와 최소높이 차이를 return

⑵ 종료 조건: 덤프 횟수 이내에 평탄화가 완료되면 더이상 덤프 수행x

 

-동작

//정렬을 미리 수행하면 최솟값, 최댓값을 찾기위한 코드를 작성하지 않고 배열의 양 끝값만 고려할 수 있습니다.

Arrays.sort(arr) = dump에 들어온 arr를 오름차순 정렬하여 제일 높은 상자의 높이 = 배열의 끝 원소값, 제일 낮은 상자의 높이 = 배열의 첫 원소값

arr[arr.length-1]-=1; //가장 높은 곳 -1
arr[0]+=1; //가장 낮은 곳 +1
Arrays.sort(arr); 
return dump(num-1, arr);//dump횟수 -1하고 다시 dump 재귀함수 호출