Softeer - 업무처리

문제 링크

문제 풀이

업무 조직은 완전 이진 트리 구조로 구성되어있다. 완전 이진 트리의 높이가 H이기에, 2^H + 1 크기의 배열로 트리를 관리할 수 있다. Queue를 이용해 대기해야하는 업무를 저장하고, 루트에서부터 탐색해나가며 대기 업무를 자녀에서 빼고 자신의 인덱스 큐에 저장하는 방식으로 문제를 풀이할 수 있다.

정답코드

import java.io.*;
import java.util.*;

public class Main {
    static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));

    int[] inputArray;
    int H, K, R, N;
    Queue<Integer>[] workers;
    int[][] works;

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.init();
        main.solve();
    }

    int[] getInputArray() throws IOException {
        return Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    void init() throws IOException {
        inputArray = getInputArray();
        H = inputArray[0];
        K = inputArray[1];
        R = inputArray[2];
        N = (int) Math.pow(2, H + 1);

        workers = new Queue[N];
        works = new int[(int) Math.pow(2, H)][K];
        for (int i = 0; i < N; i++) {
            workers[i] = new LinkedList<>();
        }
        for (int i = 0; i < (int) Math.pow(2, H); i++) {
            works[i] = getInputArray();
        }
    }

    void solve() {
        int day = 1;
        while (day <= R) {
            for (int i = 1; i < N; i++) {
                int lc = i * 2;
                int rc = i * 2 + 1;
                if (lc < N) {
                    if (day % 2 == 1) {
                        if (!workers[lc].isEmpty()) {
                            workers[i].add(workers[lc].remove());
                        }
                    } else {
                        if (!workers[rc].isEmpty()) {
                            workers[i].add(workers[rc].remove());
                        }
                    }
                } else {
                    if (day <= K) {
                        workers[i].add(works[i - (int) Math.pow(2, H)][day-1]);
                    }
                }
            }
            day += 1;
        }
        int result = 0;
        while (!workers[1].isEmpty()) {
            result += workers[1].remove();
        }
        System.out.println(result);
    }
}