[sof] 소프티어 <인증평가 5차 기출> 업무 처리 - 이진 트리

[문제]

https://softeer.ai/practice/info.do?idx=1&eid=1256&sw_prbl_sbms_sn=172419 

Softeer

 

[풀이]

1. 높이가 h인 이진트리의 노드의 개수는 2^(h+1) - 1 이고, 리프 노드의 개수는 2^h 개이다. 각 업무는 올라온 순서대로 처리하므로 Queue<Integer>[][] 배열을 이진트리 노드의 개수만큼 만든다. 이때, 리프노드를 제외한 노드들은 모두 홀수일에는 왼쪽 부하가 올린 일을, 짝수일에는 오른쪽 부하가 올린 일을 처리한다. 따라서 2차원 배열로 만들어서 왼, 오른쪽을 구분할 수 있도록 한다.

2. r일 동안 일을 처리한다. 이진트리에서 자신의 상사 노드의 인덱스는 (i+1)/2이다. (0부터 시작 시) 리프노드는 홀수, 짝수일에 상관없이 일을 처리해서 상사에 올리고, 중간 노드들과 부서장 노드는 홀수, 짝수일에 따라 왼쪽, 오른쪽 부하로부터 올라온 일을 처리하도록 한다.

 

[코드]

 

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


public class Main
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int h = Integer.parseInt(st.nextToken()); //이진트리 높이
        int k = Integer.parseInt(st.nextToken()); //k개의 일
        int r = Integer.parseInt(st.nextToken()); //r일 동안 처리

        int leaf = (int)Math.pow(2, h); //리프노드 개수
        int n = (int)Math.pow(2, h+1) - 1; //전체노드 개수

        Queue<Integer>[][] tasks = new Queue[n][2]; //왼쪽 자식, 오른쪽 자식 방향 구분 
        for(int i=0; i<n; i++){
            for(int j=0; j<2; j++){
                tasks[i][j] = new LinkedList<>();
            }
        }

        for(int i=n-leaf; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<k; j++){
                tasks[i][0].add(Integer.parseInt(st.nextToken()));
            }
        }

        //r일 동안 일을 처리
        int answer = 0;
        int day = 1;
        while(day <= r){
            //부서장은 홀수일에 왼쪽 일을, 짝수일에 오른쪽 일을 처리해서 완료한다.
            if(day%2==1 && !tasks[0][0].isEmpty()){
                answer += tasks[0][0].poll();
            }
            else if(day%2==0 && !tasks[0][1].isEmpty()){
                answer += tasks[0][1].poll();
            }

            //중간 직원은 홀수일에 왼쪽 일을, 짝수일에 오른쪽 일을 처리해서 올린다
            for(int i=1; i<n-leaf; i++){
                int parent = (i-1)/2;
                if(day%2==1 && !tasks[i][0].isEmpty()){ //홀수일
                    int task = tasks[i][0].poll();
                    if(i%2==1){ //본인이 왼쪽 자식
                        tasks[parent][0].offer(task);
                    }
                    else{ //오른쪽 자식
                        tasks[parent][1].offer(task);
                    }
                }
                else if(day%2==0 && !tasks[i][1].isEmpty()){ //짝수일
                    int task = tasks[i][1].poll();
                    if(i%2==1){ //본인이 왼쪽 자식
                        tasks[parent][0].offer(task);
                    }
                    else{ //오른쪽 자식
                        tasks[parent][1].offer(task);
                    }
                }
            }

            //말단 직원은 일을 바로 처리해서 올린다
            for(int i=n-leaf; i<n; i++){
                int parent = (i-1)/2;
                if(!tasks[i][0].isEmpty()){
                    int task = tasks[i][0].poll();
                    if(i%2==1){ //왼쪽 자식
                        tasks[parent][0].offer(task);
                    }
                    else{ //오른쪽 자식
                        tasks[parent][1].offer(task);
                    }
                }
            }

            day++;
        }

        System.out.println(answer);
           
    }

}