[Softeer] 업무 처리 (★★★☆☆)

문제

문제 링크 : https://softeer.ai/practice/info.do?idx=1&eid=1256

---

원리

완전 이진 트리에 대한 재귀 탐색

---

 

 

나의 코드

1. 레퍼런스 코드를 보고 worker클래스를 만들어 접근하는 방식을 알게 되었고, 이진트리를 사용한다는 것을 알았으나, 아직 직접 구현은 어려워 레퍼런스에 의지하여 이해하게 되었다.

2. 자료구조의 특성상 Deque를 사용하는 것이 메모리와 시간에 유리하여 Deque를 사용했다.

public class workwork {
    static int H, K, R, answer;
    static Worker[] tree;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        H = Integer.parseInt(st.nextToken()); // 조직도 높이
        K = Integer.parseInt(st.nextToken()); // 업무량
        R = Integer.parseInt(st.nextToken()); // 날짜수

        tree = new Worker[((int) Math.pow(2, H)) * 2]; // 조직도 (최대 노드인 말단의 수는 2^H)

        init(1, 0);  // 루트상사

        for (int i = (int) Math.pow(2, H); i < (int) Math.pow(2, H + 1); i++) {  // 말단의 순서
            st = new StringTokenizer(br.readLine(), " "); // 말단에게 맡길 작업들
            for (int k = 0; k < K; k++) tree[i].job.offer(Integer.parseInt(st.nextToken())); // 말단에게 작업을 맡김 (K개 만큼)
        }

        answer = 0;
        for (int r = 1; r <= R; r++) workProcess(1, r, 0);  // 날짜별 계산 호출하여 answer에 합해짐

        System.out.println(answer);
    }

    static void workProcess(int idx, int r, int depth) {
        if (depth > H) return; // 말단이면 재귀 끝

        Worker worker = tree[idx];

        // 말단인데, 작업이 남아있다?
        if (depth == H && !worker.job.isEmpty()) {
            int job = worker.job.poll();  // 작업을 뽑아
            if (idx % 2 == 0) tree[idx / 2].leftJob.offer(job); // 본인이 상사의 왼팔이면 상사의 왼쪽 대기열에 작업을 넣어라
            else tree[idx / 2].rightJob.offer(job); // 본인이 상사의 오른팔이면 상사의 오른쪽 대기열에 작업을 넣어라
        }
        // 상사이고, 짝수날인데, 작업이 남아있다?
        else if (depth < H && r % 2 == 0 && !worker.rightJob.isEmpty()) {
            int job = worker.rightJob.poll(); // 작업을 뽑아
            if (idx == 1) answer += job; // 본인이 루트상사면 작업 시마이
            else {
                if (idx % 2 == 0) tree[idx / 2].leftJob.offer(job); // 루트가 아닌 왼팔상사면, 본인의 상사 왼쪽 대기열에 작업 넣어라
                else tree[idx / 2].rightJob.offer(job);  // 루트가 아닌 오른팔상사면, 본인의 상사 오른쪽 대기열에 작업 넣어라
            }
        }
        // 상사이고, 홀수날인데, 작업이 남아있다?
        else if (depth < H && r % 2 == 1 && !worker.leftJob.isEmpty()) {
            int job = worker.leftJob.poll(); // 작업을 뽑아
            if (idx == 1) answer += job; // 본인이 루트상사면 작업 시마이
            else {
                if (idx % 2 == 0) tree[idx / 2].leftJob.offer(job); // 루트가 아닌 왼팔상사면, 본인의 상사 왼쪽 대기열에 작업 넣어라
                else tree[idx / 2].rightJob.offer(job); // 루트가 아닌 오른팔상사면, 본인의 상사 오른왼쪽 대기열에 작업 넣어라
            }
        }

        // 이전에 올라온 작업을 처리했으니, 좌우 부하직원을 탐색해서 다시 반복
        workProcess(idx * 2, r, depth + 1);
        workProcess(idx * 2 + 1, r, depth + 1);
    }

    static void init(int idx, int depth) {
        if (depth > H) return;

        Worker newWorker = new Worker(depth);
        tree[idx] = newWorker;

        init(idx * 2, depth + 1);  // 왼쪽
        init(idx * 2 + 1, depth + 1);  // 오른쪽
    }

    static class Worker {
        int depth;
        Deque<Integer> leftJob, rightJob, job;

        public Worker(int depth) {
            this.depth = depth;
            initJob();
        }

        public void initJob() {
            if (depth == H) job = new ArrayDeque<>(); // 말단일 경우 : 가지고 있는 작업을 저장할 큐를 생성
            else { // 상사노드일 경우 : 왼쪽 부하직원 or 오른쪽 부하직원에 의해 작업을 전달받을 큐를 생성
                leftJob = new ArrayDeque<>();
                rightJob = new ArrayDeque<>();
            }
        }
    }
}

 

---

레퍼런스 코드

hyunjong96님의 레퍼런스 참고 링크 : https://velog.io/@hyunjong96/Softeer-%EC%97%85%EB%AC%B4-%EC%B2%98%EB%A6%AC