소프티어 5회 기출 - 업무 처리

난이도 - Lv3

사용 개념 - 구현, 자료구조( 다중 Queue)

풀이 시간 -  40분 ( 설계 25분, 구현 15분 )

핵심 키워드

1. 말단 직원은 왼쪽, 오른쪽의 구분이 없이 하루에 하나씩 업무를 처리한다.

2. 중간직원과 부서장은 홀수 날에는 왼쪽 직원이 보낸 업무를, 짝수 날에는 오른쪽 직원이 보낸 업무를 처리한다.

-> 말단 직원이 일을 올려보내고 하루가 지나야 상사들이 일을 시작할 수 있음.

-> 부서는 완전 이진트리로 되어있기 때문에 트리를 구현하면 가능함.

3. 왼쪽, 오른쪽의 구분이 있기 때문에 Queue[][] 2차원 배열을 사용하여 각 사원들이 왼쪽업무, 오른쪽 업무를 가져갈 수 있게끔 하였음.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static StringTokenizer st;
    static StringBuilder sb;
 
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine(), " ");
        int h = Integer.parseInt(st.nextToken()); // 트리의 높이
        int k = Integer.parseInt(st.nextToken()); // 업무의 수  1명당 맡은 업무의 수임.
        int r = Integer.parseInt(st.nextToken()); // 날의 수
        int width = (int)Math.pow(2, h); // 말단 직원의 수
        int n = (int)Math.pow(2, h+1)-1; // 전체 노드의 수
        Queue<Integer>[][] queues = new Queue[n][2];
        for(int i=0; i<n; i++){
            for(int j=0; j<2; j++){
                queues[i][j] = new ArrayDeque<>();
            }
        }
 
        for(int i=n-width; i<n; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<k; j++){
                queues[i][0].offer(Integer.parseInt(st.nextToken())); // 말단들은 왼쪽 오른쪽 구분이 없단다
            }
        }
 
        int result = 0;
        int day = 1;
        while(day<=r){
            int bit = day%2;
            if(bit==1 && !queues[0][0].isEmpty()){ // 홀수 날? 그럼 왼쪽 처리
                result+=queues[0][0].poll();
            }
            else if(bit==0 && !queues[0][1].isEmpty()){ // 짝수 날? 그럼 오른쪽 처리
                result+=queues[0][1].poll();
            }
 
            for(int i=1; i<n-width; i++){
                int parent = (i-1)/2;
                if(bit==1 && !queues[i][0].isEmpty()){ // 홀수 날? 그럼 왼쪽 처리
                    int poll = queues[i][0].poll();
                    if(i%2==1){
                        queues[parent][0].offer(poll); // 왼쪽 자식은 부모의 왼쪽에 넣거라
                    }
                    else{
                        queues[parent][1].offer(poll); // 오른쪽 자식..
                    }
                }
                else if(bit==0 && !queues[i][1].isEmpty()){ // 짝수 날? 그럼 오른쪽 처리
                    int poll = queues[i][1].poll();
                    if(i%2==1){
                        queues[parent][0].offer(poll); // 왼쪽 자식은 부모의 왼쪽에 넣거라
                    }
                    else{
                        queues[parent][1].offer(poll); // 오른쪽 자식..
                    }
                }
            }
 
            for(int i=n-width; i<n; i++){
                int parent = (i-1)/2;
                if(!queues[i][0].isEmpty()){ // 비어있지 않다면용
                    if(i%2==1){
                        queues[parent][0].offer(queues[i][0].poll()); // 왼쪽 자식은 부모의 왼쪽에 넣거라
                    }
                    else if(i%2==0){
                        queues[parent][1].offer(queues[i][0].poll()); // 오른쪽 자식..
                    }
                }
            }
            day++;
        }
        System.out.println(result);
    }
}

 

 

- 말단 직원이 업무를 올릴 때 왼쪽 자식인지, 오른쪽 자식인지에 따라 부모의 왼쪽, 오른쪽 업무가 나뉘는데 이것을 구현 및 생각하는데 시간이 좀 걸린 문제

- 중간 직원 역시 자신의 조상에게 업무를 올릴 때의 메커니즘이 말단 직원과 같다는 사실을 간과했었음.