Softeer - 업무 처리

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

---

Problem

---

Solve

문제를 이해하는데 많은 시간이 소요된 문제였습니다.

문제를 요약하자면

• 말단 직원은 각 날짜에 남은 업무가 있다면 하나씩 작업을 수행하여 상사에게 작업을 올립니다.
• 상사는 당일 올라온 작업이 아닌 이전에 올라온 작업을 하루에 한개씩 처리합니다.
• 상사는 홀수 번째 날에는 왼쪽 부하 직원이 올린 업무를 처리하고 짝수 번째 날에는 오른쪽 부하 직원이 올린 업무를 처리합니다.
• 루트(부서장)가 처리한 작업의 합을 계산합니다. (루트도 다른 상사와 마찬가지로 날짜에 따라 다른쪽 부하 직원이 올린 업무를 하나씩 처리합니다.)

이 문제를 구현하기 위해 완전 이진트리를 사용하였습니다.
그리고 각 날짜마다 루트부터 각 말단 직원까지 탐색하면서 상사일 경우 날짜별로 왼쪽과 오른쪽에서 올라온 이전 작업을 처리하고 부하 직원을 탐색합니다. 말단 직원일 경우 작업이 존재하는 경우 작업을 처리하였습니다.

아래 코드는 특정 날짜에 모든 노드를 탐색하며 위의 작업을 구현한 것입니다.

	static void workProcess(int idx, int r, int depth){
    	//말단 노드의 depth는 H이기 때문에 H를 넘어가면 재귀를 종료합니다.
		if(depth > H) return;

		//트리는 루트를 idx=1로 선언하고 왼쪽 노드는 idx*2, 오른쪽 노드는 idx*2+1로 선언하였습니다.
		Worker worker = tree[idx];
        
        //말단 노드이고 작업이 존재하는 경우
		if(depth == H && !worker.job.isEmpty()){
			int job = worker.job.poll();
            //상사 노드의 왼쪽에 존재하는 말단 노드는 상사 노드의 왼쪽job에 작업을 올립니다.
			if(idx%2==0) tree[idx/2].leftJob.offer(job);
            //오른쪽에 존재한다면 오른쪽job에 작업을 올립니다.
			else tree[idx/2].rightJob.offer(job);
		}
        //상사 노드이고 짝수 날짜인 경우
       	//짝수 날짜인데 오른쪽 작업이 존재하지 않는다면 해당 상사는 작업을 하지 않습니다.
		else if(depth < H && r%2 == 0 && !worker.rightJob.isEmpty()){
			int job = worker.rightJob.poll();
            
            //상사 노드가 루트라면 해당 작업의 합을 갱신합니다.
			if(idx==1) answer += job;
            
            //루트가 아닌 상사 노드인 경우
			else{
            	//해당 노드가 상사의 왼쪽 노드라면 상사의왼쪽job에, 오른쪽 노드라면 상사의 오른쪽job에 작업을 올립니다.
				if(idx%2==0) tree[idx/2].leftJob.offer(job);
				else tree[idx/2].rightJob.offer(job);
			}
		}
        //상사 노드이고 홀수 날짜인 경우
        //오른쪽 작업이 존재하지 않는다면 작업하지 않습니다.
        else if(depth < H && r%2 == 1 && !worker.leftJob.isEmpty()){
			int job = worker.leftJob.poll();
            
            //해당 노드가 루트라면 작업의 합을 갱신합니다.
			if(idx==1) answer += job;
            //루트가 아닌 상사 노드인 경우 상사의 상사 노드에 날짜에 따라 작업을 올려줍니다.
			else{
				if(idx%2==0) tree[idx/2].leftJob.offer(job);
				else tree[idx/2].rightJob.offer(job);
			}
		}

		//이전에 해당 노드로 올라온 작업을 처리했다면 부하 직원을 탐색하여 이를 반복해줍니다.
		workProcess(idx*2, r, depth+1);
		workProcess(idx*2+1, r, depth+1);
	}
    
    static class Worker{
		int depth;
		Queue<Integer> leftJob;
		Queue<Integer> rightJob;
		Queue<Integer> job;

		public Worker(int depth){
			this.depth = depth;
			initJob();
		}

		//상사노드라면 왼쪽, 오른쪽 부하 직원에서 올라온 작업을 저장할 큐를 정의
        //말단노드라면 가지고있는 작업을 저장할 큐를 정의
		public void initJob(){
			if(depth == H){
				job = new LinkedList<>();
			}else{
				leftJob = new LinkedList<>();
				rightJob = new LinkedList<>();
			}
		}
	}

위의 코드를 보시면 작업은 오늘이 아닌 이전에 올라온 작업을 먼저 처리하고 오늘 처리할 작업을 상사 노드에 올려주고 있습니다. 그 후 부하 노드를 탐색하여 이를 반복하도록 구현하였습니다.

참고로 트리는 배열을 통해 배열의 1번 idx를 루트로 선언하고 왼쪽 자식노드를 idx2, 오른쪽 자식노드를 idx2+1로 선언하여 구성하였습니다.

트리의 배열크기는 최적화를 찾지 못하여 완전 이진트리의 말단 노드의 개수(2의 H제곱)의 곱으로 선언하였습니다.

---

Code

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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		H = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());

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

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

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static void workProcess(int idx, int r, int depth){
		if(depth > H) return;

		Worker worker = tree[idx];
		if(depth == H && !worker.job.isEmpty()){
			int job = worker.job.poll();
			if(idx%2==0) tree[idx/2].leftJob.offer(job);
			else tree[idx/2].rightJob.offer(job);
		}
		else if(depth < H && r%2 == 0 && !worker.rightJob.isEmpty()){
			int job = worker.rightJob.poll();
			if(idx==1) answer += job;
			else{
				if(idx%2==0) tree[idx/2].leftJob.offer(job);
				else tree[idx/2].rightJob.offer(job);
			}
		}else if(depth < H && r%2 == 1 && !worker.leftJob.isEmpty()){
			int job = worker.leftJob.poll();
			if(idx==1) answer += job;
			else{
				if(idx%2==0) tree[idx/2].leftJob.offer(job);
				else tree[idx/2].rightJob.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> leftJob;
		Queue<Integer> rightJob;
		Queue<Integer> job;

		public Worker(int depth){
			this.depth = depth;
			initJob();
		}

		public void initJob(){
			if(depth == H){
				job = new LinkedList<>();
			}else{
				leftJob = new LinkedList<>();
				rightJob = new LinkedList<>();
			}
		}
	}
}

---

Result

---

Reference