(softeer) lv.3 업무처리

오랜만에 강적 머리 아픈 문제 ^^

완전 이진 트리, 빡구현 문제 

 

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

 

문제 요약

- H = 트리 높이, K = 일의 갯수 , R= 일 기간

- 말단 직원들에게 순서가 있는 업무 K개가 R일 동안 주어진다.

- 각 직원 별로 진행하는 일이 다름 (홀수 날 - 왼쪽 부하, 짝수날- 오른쪽 부하)

부서장 : 최종 승인 ( 번호 합 )

중간 직원 : 날짜별로 위에 보고처리

말단 직원 : 무조건 1일에 1개씩 위에 보고 처리

 

 

문제 풀이

문제를 이해하는데 좀 오래걸렸는데, 

소프티어에서 제공한 입력 예시2로 쉽게 말하면

(입력 예시2)

H = 1 , K = 3, R =2

9 3 7 

5 11 2

 

1일째는

부서장은 보고된 일 X

왼쪽 말단 직원이 일(9) 처리를 해서 부서장에게 보고,

오른쪽 말단 직원이 일(5) 처리를 해서 부서장에게 보고

 

2일째는 

부서장에게 보고된 2가지 업무중, 짝수날이니까 오른쪽 직원이 한 일(5)를 승인

 

= 답 :5 

 

하지만 H=2 이상이 되는 순간, 부서장-말단 직원 뿐만 아니라 부서장-중간 직원-말단직원이 되버려서 유의해야한다.

심지어 왼쪽 부하가 보고한건지, 오른쪽 부하가 보고한건지 확인하여 따로 저장해야하기때문에 

각 노드마다의 Queue<Integer>[][] 가 필요 하다 .. ㅠㅠ

 

 

 

 

코드

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

public class Main {
    static int H,K,R;
    static int task[][];
    static int ans;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        int n=0; // 말단 직원의 수
        n = (int)Math.pow(2,H);
        
        int mem=0; //전체 직원의 수
        mem = (int)Math.pow(2,H+1)-1;
        
        task = new int[n][K];

    
        //전체 직원의 왼,오 자식에서 받은 data
        Queue<Integer>[][] que = new Queue[mem][2];
        
        for(int i=0; i<mem; i++){
            for(int j=0; j<2; j++){
                que[i][j] = new LinkedList<>();
            }
        }

        //말단직원의 할일 입력
        for(int i=mem-n;i<mem;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<K;j++){
                que[i][0].add(Integer.parseInt(st.nextToken()));
                //그냥 왼쪽에 입력한거
                }
        }
        
        int day =1;        
        //r 일동안 업무 보고 반복
        while(day<=R){
            //부서장 - 최종 승인
            if(day%2==0 && !que[0][1].isEmpty() ){
                ans+= que[0][1].poll();
            }
            else if(day%2==1 && !que[0][0].isEmpty() ){
                ans+= que[0][0].poll();
            }
            
            //중간 직원 - 홀수일에 왼쪽일 처리, 짝수일에 오른쪽일 처리
            for(int i=1; i<mem-n;i++){
                
                int par = (i-1)/2;
                int idx = 0;
                
                if(i%2==0) idx=1;
                
                if(day%2==0 && !que[i][1].isEmpty() ){
                    int tmp = que[i][1].poll();
                    que[par][idx].add(tmp);
                }
                else if(day%2==1 && !que[i][0].isEmpty() ){
                    int tmp = que[i][0].poll();
                    que[par][idx].add(tmp);
                }     
            }
            
            //말단 - 옮김
            for(int i=mem-n;i<mem;i++){
                 if(!que[i][0].isEmpty()){
                    int tmp = que[i][0].poll();
                    if(i%2==0)
                        que[ (i-1)/2 ][1].add(tmp);
                    else
                        que[ (i-1)/2 ][0].add(tmp);
                    }
                }
            day++;
            
        }

    
        
        
        System.out.println(ans);
    }
}