[SW Expert Academy / JAVA] 1208.1일차 - Flatten

이번에 풀어볼 문제는 1208번 1일차 - Flatten이다.

SW Expert Academy

 

우선 문제부터 보자.

 

문제 설명

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

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

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

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

 

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

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

 

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

다음은 제2회 덤프를 수행한 이후의 화면이다.
 

 

A’부분의 상자를 옮겨서, C부분에 덤프 하였다. 이때 C 대신 C’ 부분에 덤프 해도 무방하다.

2회의 덤프 후, 최고점과 최저점의 차이는 8 – 2 = 6 이 되었다 (최초덤프 이전에는 9 – 1 = 8이었다).

덤프 횟수가 2회로 제한된다면, 이 예시 문제의 정답은 6이 된다.

 

음 대충 정렬 문제인 거 같다 평탄화 작업을 한 뒤 최고점 최저점을 찾아보도록 하겠다.

 

그럼 그다음으로 조건을 보자

 

제약 사항

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

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

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

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

 

 

 

그다음은 입, 출력이다.

입력

 

834
42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 92 96 43 28 37 92 5 3 54 93 83 22 17 19 96 ...
617
16 40 59 5 31 78 7 74 87 22 46 25 73 71 30 78 74 98 13 87 91 62 37 56 68 56 75 32 53 ...
...

출력

 

#1 13
#2 32
...

 

 

음 나는 Arrays의 정렬을 사용하여 풀겠다.

 

코드를 보자.

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int sum = 0;
        for(int i = 0; i < 10; i++){
            int dump = sc.nextInt();
            sc.nextLine();
            String[] data = sc.nextLine().split(" ");
            int[] arr = Arrays.stream(data).mapToInt(Integer::parseInt).toArray();
            Arrays.sort(arr);
            for(int j = 0; j < dump; j++){
                arr[0]++;
                arr[99]--;
                Arrays.sort(arr);
            }

            System.out.println("#" + (i+1) + " " + (arr[99] - arr[0]));
        }

    }

 

우선 data를 String배열로 받은 뒤, int배열로 mapToInt를 사용해 바꿔준다. (이거 유용하니 알고 있으면 좋다.)

 

그다음 정렬해주고,

정렬을 했으니 0번 인덱스가 가장 작은 수, 99번 인덱스가 가장 높은 수 일 것이다. ( 문제에서 무조건 배열의 길이는 100이라고 주었으니 인덱스는 숫자로)

0번째를 하나 더해주고,

99번째를 하나 빼준다.

그리고 다시 정렬.

이거를 받은 횟수(dump)만큼 반복하면 끝이다.

 

이번 문제는 조금만 생각하면 답이 나오는 수준이어서 쉬운 것 같다.