[SWEA] #1208 - Flatten

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

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

SW Expert Academy

 

💡 문제

---

[설명]

한 쪽 벽면에 다음과 같이 노란색 상자들이 쌓여 있다.

높은 곳의 상자를 낮은 곳에 옮기는 방식으로 최고점과 최저점의 간격을 줄이는 작업을 평탄화라고 한다.

평탄화를 모두 수행하고 나면, 가장 높은 곳과 가장 낮은 곳의 차이가 최대 1 이내가 된다.

평탄화 작업을 위해서 상자를 옮기는 작업 횟수에 제한이 걸려있을 때, 제한된 횟수만큼 옮기는 작업을 한 후 최고점과 최저점의 차이를 반환하는 프로그램을 작성하시오.

가장 높은 곳에 있는 상자를 가장 낮은 곳으로 옮기는 작업을 덤프라고 정의한다.

위의 예시에서 제1회 덤프를 수행한 이후 화면은 다음과 같다.

A부분의 상자를 가장 낮은 B부분에 덤프하였으며, A대신 A’부분의 상자를 사용해도 무방하다.

 

[제약 사항]

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

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

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

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

 

💡 아이디어

---

큰 아이디어는 가장 높은 상자의 높이를 분배해 모든 상자의 높이를 비슷하게 맞추는 것이다.

그러기 위해선 매번 정렬을 한 다음에 가장 높은 지점에서 가장 낮은 지점으로 높이를 1씩 나눠주면 된다.

덤프횟수가 주어지므로 덤프횟수만큼 반복하고 마지막에 정렬을 한 번 더 진행해

최소값과 최대값의 차이를 반환하면 된다. 

 

💡 소스코드

---

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

public class P_1208 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int Dump, Difference = 0;//Dump : 주어진 횟수,  Difference : 최고점 - 최저점
		int[] array = new int[101];

		for (int test_case = 1; test_case <= 10; test_case++) {
			Dump = sc.nextInt();//Dump 입력 받기

			for (int i = 1; i <= 100; i++)
				array[i] = sc.nextInt();//array[]에 각 높이 저장

			for (int j = 1; j <= Dump; j++) {
				Arrays.sort(array);//array[] 정렬
				/*정렬된 높이에서 최고높이는 -1, 최소높이는 +1 => Dump만큼 반복*/
				array[1]++;
				array[100]--;
			}

			Arrays.sort(array);//다시 정렬
			Difference = array[100] - array[1];//최종 높이차

			System.out.println("#" + test_case + " " + Difference);//출력
		}
	}
}

 

💡 결과

---

문제에서는 가로 길이를 100으로 제한했다.

그렇기 때문에 아마 시간제한에 걸리지 않고 문제가 해결될 수 있었던 것 같다.

Arrays.sort()는 Dual Pivot QuickSort로  평균 O(nlog(n))의 시간복잡도를 가지며 최악의 경우 O(n^2)를 가진다.

즉, 주어진 테스트 케이스가 최악이라면 Arrays.sort를 사용했을 때 시간은 선형적으로 증가할 것이다.

조금 다르게 문제를 접근할 필요가 있어보인다.