[Softeer] Java - level3 문제풀이(업무처리)

softeer 업무처리(Java)

[문제]

어떤 부서의 업무 조직은 완전이진트리 모양이다. 즉, 부서장이 루트이고 부서장 포함 각 직원은 왼쪽과 오른쪽의 부하 직원을 가진다. 부하 직원이 없는 직원을 말단 직원이라고 부른다.

 

모든 말단 직원은 부서장까지 올라가는 거리가 동일하다. 조직도 트리의 높이는 H이다. 아래는 높이가 1이고 업무가 3개인 조직도를 보여준다.

 

 

업무는 R일 동안 진행된다. 처음에 말단 직원들만 각각 K개의 순서가 정해진 업무를 가지고 있다. 각 업무는 업무 번호가 있다. 각 날짜에 남은 업무가 있는 경우, 말단 직원은 하나의 업무를 처리해서 상사에게 올린다. 다른 직원들도, 대기하는 업무가 있는 경우 업무를 올라온 순서대로 하나 처리해서 상사에게 올린다. 단, 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무를 처리한다.

 

부서장이 처리한 일은 완료된 것이다. 업무를 올리는 것은 모두 동시에 진행한다. 따라서 그날 올린 업무를 상사가 처리하는 것은 그 다음날에야 가능하다.

 

부서의 조직과 대기하는 업무들을 입력 받아 처리가 완료된 업무들의 번호의 합을 계산하는 프로그램을 작성하라.

 

[제약조건]

1 ≤ H ≤ 10

1 ≤ K ≤ 10

1 ≤ R ≤ 1,000

 

[입력형식]

첫 줄에 조직도의 높이 H, 말단에 대기하는 업무의 개수 K, 업무가 진행되는 날짜 수 R이 주어진다.

그 다음 줄부터 각각의 말단 직원에 대해 대기하는 업무가 순서대로 주어진다.

제일 왼쪽의 말단 직원부터 순서대로 주어진다.

 

[출력형식]

완료된 업무들의 번호 합을 정수로 출력한다.

 

[풀이]

이진탐색에 대한 기초지식이 많이 부족해서 공부도 나름 많이 하고 접근했지만, 새로 사용해보는 Queue와 LinkedList 자료형에 아직 완벽히 이해를 하지는 못했습니다. 혼자서 문제를 풀려다 실패하고 아래 블로그를 참고해서 풀었습니다.

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


public class Main
{
    static int H;
    static int K;
    static int R;
    static worker[] tree;
    static int answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        H = Integer.parseInt(input[0]);
        K = Integer.parseInt(input[1]);
        R = Integer.parseInt(input[2]);

        tree = new worker[(int) Math.pow(2, H + 1)];
        init(1, 0);
        for(int i=(int)Math.pow(2,H); i<(int)Math.pow(2,H+1); i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<K; j++) {
                tree[i].job.offer(Integer.parseInt(st.nextToken()));
            }
        }

        answer = 0;
        for(int i=1; i<=R; i++) {
            workProcess(1, i, 0);
        }

        System.out.println(answer);
    }

    static void workProcess(int idx, int r, int depth) {
        if(depth>H) return;
        worker nowWorker = tree[idx];
        if(depth == H && !nowWorker.job.isEmpty()) {
            int job = nowWorker.job.poll();
            if(idx%2==0) tree[idx / 2].left.offer(job);
            else tree[idx / 2].right.offer(job);
        } else if(depth<H && r%2==0 && !nowWorker.right.isEmpty()) {
            int job = nowWorker.right.poll();
            if(idx == 1) answer += job;
            else {
                if(idx%2 == 0) tree[idx / 2].left.offer(job);
                else tree[idx / 2].right.offer(job);
            }
        } else if(depth<H && r%2==1 && !nowWorker.left.isEmpty()) {
            int job = nowWorker.left.poll();
            if(idx == 1) answer += job;
            else {
                if(idx%2 == 0) tree[idx / 2].left.offer(job);
                else tree[idx / 2].right.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;
        Queue<Integer> left;
        Queue<Integer> right;
        Queue<Integer> job;
        public worker(int depth) {
            this.depth = depth;
            initJob();
        }
        public void initJob() {
            if(depth == H) {
                job = new LinkedList<>();
            }else {
                left = new LinkedList<>();
                right = new LinkedList<>();
            }
        }
    }
}

 

https://velog.io/@hyunjong96/Softeer-%EC%97%85%EB%AC%B4-%EC%B2%98%EB%A6%AC