[소프티어] 6251번 - 업무 처리 [Java]

https://softeer.ai/practice/6251

 

[소프티어] 6251번 - 업무 처리 [Java]

[소프티어] 6251번 - 업무 처리 [Java]

[소프티어] 6251번 - 업무 처리 [Java]

---

1.  아이디어

 

각 직원에 대해 왼쪽 직원한테 받은 업무와 오른쪽 직원한테 받은 업무를 구분해야 한다. 이를 위해 두 개의 Queue를 갖는 노드 클래스를 활용했고 주어진 트리의 루트를 1로 설정한 후 비트마스킹을 활용했다. 업무의 전달은 부서장부터 말단 직원 순으로 진행된다는 점에 주의해야한다.

---

2. 문제풀이

 

완전이진트리인데 말단 직원과 부서장까지의 올라가는 거리가 같으면 포화이진트리가 된다. 이를 통해 가장 왼쪽 말단 직원의 번호와 가장 오른쪽 말단 직원의 번호를 비트마스킹으로 구해서 변수로 저장했다. 이후 말단 직원에게 업무들을 부여했다.

 

R일까지의 반복은 부서장 일처리 -> 중간 직원 일처리 -> 말단 직원 일처리 순서로 진행되며 역시 비트마스킹을 활용해서 트리의 높이별로 진행하도록 구현했다. 이때 홀수일 짝수일과 해당 직원의 번호가 홀수인지 짝수인지를 고려해서 조건을 설정했다. 트리에서 왼쪽 자식은 항상 번호가 짝수고 오른쪽 자식은 항상 번호가 홀수번이 된다.

---

3. 코드

 

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

public class Main {

    private static class Node {
        // 왼쪽 부하 직원이 올린 업무들
        Queue<Integer> left = new ArrayDeque<>();
        // 오른쪽 부하 직원이 올린 업무들
        Queue<Integer> right = new ArrayDeque<>();
    }

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

        int H = Integer.parseInt(st.nextToken()) + 1;
        int K = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        // 완전이진트리면서 말단 직원과 부서장까지 올라가는 거리가 동일하면 포화이진트리(부서장을 1로 설정)
        Node[] tree = new Node[1 << H];
        for (int i = 0; i < (1 << H); i++) {
            tree[i] = new Node();
        }

        // 가장 왼쪽 말단 직원의 번호
        int leafStart = 1 << (H - 1);
        // 가장 오른쪽 말단 직원의 번호
        int leafEnd = (1 << H) - 1;

        // 말단 직원에게 대기하는 업무를 넣어줌
        // 상사의 왼쪽 말단 직원이면 그냥 왼쪽 큐에, 오른쪽 말단 직원이면 오른쪽 큐에 삽입
        for (int i = leafStart; i <= leafEnd; i++) {
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                if (i % 2 == 0) tree[i].left.add(Integer.parseInt(st.nextToken()));
                else tree[i].right.add(Integer.parseInt(st.nextToken()));
            }
        }

        int sum = 0;
        for (int day = 1; day <= R; day++) {

            // 부서장이 일 처리
            if (day % 2 == 1 && !tree[1].left.isEmpty()) sum += tree[1].left.remove();
            else if (day % 2 == 0 && !tree[1].right.isEmpty()) sum += tree[1].right.remove();

            // 중간 직원이 일 처리
            for (int h = 2; h < H; h++) {

                // 현재 높이에서 가장 왼쪽 중간 직원의 번호
                int left = 1 << (h - 1);
                // 현재 높이에서 가장 오른쪽 중간 직원의 번호
                int right = (1 << h) - 1;

                for (int i = left; i <= right; i++) {

                    // 홀수일이면서 왼쪽 부하직원이 준 업무가 있는 경우
                    if (day % 2 == 1 && !tree[i].left.isEmpty()) {
                        int task = tree[i].left.remove();

                        // 번호가 짝수인 직원은 상사에게 왼쪽 부하 직원
                        if (i % 2 == 0) tree[i / 2].left.add(task);
                        // 번호가 홀수인 직원은 상사에게 오른쪽 부하 직원
                        else tree[i / 2].right.add(task);
                    }
                    // 짝수일이면서 오른쪽 부하직원이 준 업무가 있는 경우
                    else if (day % 2 == 0 && !tree[i].right.isEmpty()) {
                        int task = tree[i].right.remove();

                        // 번호가 짝수인 직원은 상사에게 왼쪽 부하 직원
                        if (i % 2 == 0) tree[i / 2].left.add(task);
                        // 번호가 홀수인 직원은 상사에게 오른쪽 부하 직원
                        else tree[i / 2].right.add(task);
                    }
                }
            }

            // 말단 직원이 일 처리
            for (int i = leafStart; i <= leafEnd; i++) {
                // 번호가 짝수인 직원은 상사에게 왼쪽 부하 직원
                if ((i % 2 == 0) && !tree[i].left.isEmpty()) tree[i / 2].left.add(tree[i].left.remove());
                // 번호가 홀수인 직원은 상사에게 오른쪽 부하 직원
                else if ((i % 2 == 1) && !tree[i].right.isEmpty()) tree[i / 2].right.add(tree[i].right.remove());
            }
        }

        System.out.println(sum);
    }
}

---

4. 후기