1208. Flatten [#1차원 배열]

 

---

1. 문제 출처

---

SW Expert Academy

 

 

 

---

2. 설계

---

- Arrays.sort를 이용해 높이순으로 정렬한다.

- 가장 뒤에 있는 블록의 높이가 크므로, 가장 앞에 있는 블록에 1개를 충당한다.

- 위 2단계를 반복해 둘 사이 높이 차가 0이 되면 멈추고, 그 전에 횟수가 끝나면 차를 반환한다.

 

 

---

3. 전체 코드

---

import java.util.Scanner;
import java.io.FileInputStream;
import java.util.Arrays;
 
class Solution
{
    public static void main(String args[]) throws Exception
    {
         
        Scanner sc = new Scanner(System.in);
         
        for(int T=1;T<=10;T++) {
            int dump = sc.nextInt();
            int[] box_height = new int[100];
            for(int i=0;i<100;i++) {
                box_height[i]=sc.nextInt();
            }
             
            //입력 끝
             
            for(int i=0;i<dump;i++) {
                Arrays.sort(box_height);
                if(box_height[99]-box_height[0]!=0) {
                    box_height[99]--;
                    box_height[0]++;
                }else {
                    break;
                }
            }
            Arrays.sort(box_height);
            System.out.println("#"+T+" "+(box_height[99]-box_height[0]));
             
        }
    }
}

 

고민했던 것은 맨 첫 블록과 맨 뒤 블록의 차가 1일 때이다.

99와 100일 때 맨 앞 블록이 역전되어 버리는데, 0일 때가 아니라 1일 때부터 멈춰야하는건가 생각했다.

[99 99 100 100] -> [100 99 100 99] -> sort -> [99 99 100 100]

dump 수까지 같은 상황이 반복된다.

 

차가 1일 때 멈추지 않아도 답에는 영향이 없을 것이라 판단해서

더욱 정확히 차이가 0이 될 때, 평탄화가 완벽할 때만 break하게 했다.