[S/W 문제해결 기본] 1일차 - Flatten (D3)

문제 링크

• 높낮이가 다른 상자들을 옮겨서 차이를 줄이는 문제이다.
• 상자를 옮기는 작업을 덤프라고 하는데 덤프의 횟수가 제한되고,
• 덤프 횟수동안 평탄화를 진행한 후에 가장 높은 상자와 낮은 상자의 차이를 출력한다.
• 덤프 횟수 내에 평탄화가 완료되면 return

Solution

Arrays.sort()를 사용하면 금방 풀 수 있지만! sort() 구현을 배우는 중이라 구현해서 풀었다.

package swea;
//[S/W 문제해결 기본] 1일차 - Flatten
import java.util.Scanner;

public class p1208 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for (int t = 1; t <= 10; t++) {
			int dump = sc.nextInt();
			int[] box = new int[100];
			for (int i = 0; i < 100; i++) {
				box[i] = sc.nextInt();
			}
			
			//sort 안쓰기
			for (int i = 0; i < dump; i++) {
				for (int j = 0; j < 99; j++) {
					for (int k = 0; k < 99 - j; k++) {
						if (box[k] > box[k + 1]) {
							int tmp = box[k];
							box[k] = box[k + 1];
							box[k + 1] = tmp;
						}
					}
				}
				if (box[99] - box[0] == 0) { // 덤프 횟수 내에 평탄화가 완료됐다면 그냥 종료
					break;
				}
				box[99] = box[99] - 1; // 높은 곳에서 하나를 빼고
				box[0] = box[0] + 1; // 낮은 곳에 올리기

			}
			// 마지막 작업으로 순서가 변했을 수도 있으니 99,98 비교 & 0,1 비교
			System.out.printf("#%d %d\n", t, Math.max(box[99], box[98]) - Math.min(box[0], box[1])); 
		}

	}
}