[1208] Flatten

✔ Flatten

[SWEA 1208]

문제 분석하기

상자들을 저장한 후 오름차순으로 정렬한 후

가장 낮은 높이의 상자 갯수에 + 1, 가장 가장 높은 높이의 상자 갯수를 -1 해주기는 것을 덤프만큼 반복 

(또는 시간 단축을 위해 Heap을 사용해서 최댓값, 최솟값 우선순위 큐를 만들어서 해결)

손으로 풀어보기

1. 100만큼의 크기 배열에 위치의 상자 높이를 저장
2. 덤프만큼 반복하며 상자의 높이들을 오름차순 정렬한 후
   가장 낮은 높이의 상자 갯수에 + 1, 가장 가장 높은 높이의 상자 갯수를 -1
3. 가장 가장 높은 높이의 상자 갯수 - 가장 낮은 높이의 상자 갯수 반환

슈도코드 작성하기

T(테스트 케이스 수) = 10
for(T만큼) {
    N(덤프의 개수)
    box(박스 높이 저장 배열 (100만큼))
    for(i -> 100만큼) {
        box[i] = 박스의 높이
    }
    for(i -> N만큼) {
        box 오름차순 정렬
        가장 낮은 높이의 상자 갯수에 + 1
        가장 가장 높은 높이의 상자 갯수를 -1
    }   
    box 오름차순 정렬
    #T와 가장 가장 높은 높이의 상자 갯수 - 가장 낮은 높이의 상자 갯수 반환
}

코드 구현하기

/**
 * 1208) Flatten
 */
public class D003_1208 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // T(테스트 케이스 수) = 10
        int T = 10;
        // T만큼
        for (int test_case = 1; test_case <= T; test_case++) {
            // N(덤프의 개수)
            int N = sc.nextInt();
            // box(박스 높이 저장 배열 (100만큼))
            int[] box = new int[100];
            // 박스 높이 저장
            for (int i = 0; i < box.length; i++) {
                // box[i] = 박스의 높이
                box[i] = sc.nextInt();
            }
            // 덤프만큼
            for (int i = 0; i < N; i++) {
                // box 오름차순 정렬
                Arrays.sort(box);
                // 가장 낮은 높이의 상자 갯수에 + 1
                box[0]++;
                // 가장 가장 높은 높이의 상자 갯수를 -1
                box[99]--;
            }
            // box 오름차순 정렬
            Arrays.sort(box);
            // #T와 가장 가장 높은 높이의 상자 갯수 - 가장 낮은 높이의 상자 갯수 반환
            System.out.println("#" + test_case + " " + (box[99] - box[0]));
        }
    }
}