[소프티어] 업무 처리 자바 풀이 이진트리 (HSAT 5회 정기 코딩 인증평가 기출)

https://softeer.ai/practice/6251

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

언어별 시간/메모리

언어시간메모리

JavaScript	1초	256MB
C	1초	256MB
C++	1초	256MB
Java	1초	256MB
Python	1초	256MB

어떤 부서의 업무 조직은 완전이진트리 모양이다. 즉, 부서장이 루트이고 부서장 포함 각 직원은 왼쪽과 오른쪽의 부하 직원을 가진다. 부하 직원이 없는 직원을 말단 직원이라고 부른다.

 

모든 말단 직원은 부서장까지 올라가는 거리가 동일하다. 조직도 트리의 높이는 H이다. 아래는 높이가 1이고 업무가 3개인 조직도를 보여준다.

 

 

업무는 R일 동안 진행된다. 처음에 말단 직원들만 각각 K개의 순서가 정해진 업무를 가지고 있다. 각 업무는 업무 번호가 있다. 각 날짜에 남은 업무가 있는 경우, 말단 직원은 하나의 업무를 처리해서 상사에게 올린다. 다른 직원들도, 대기하는 업무가 있는 경우 업무를 올라온 순서대로 하나 처리해서 상사에게 올린다. 단, 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무를 처리한다.

 

부서장이 처리한 일은 완료된 것이다. 업무를 올리는 것은 모두 동시에 진행한다. 따라서 그날 올린 업무를 상사가 처리하는 것은 그 다음날에야 가능하다.

 

부서의 조직과 대기하는 업무들을 입력 받아 처리가 완료된 업무들의 번호의 합을 계산하는 프로그램을 작성하라.

제약조건

1 ≤ H ≤ 10

1 ≤ K ≤ 10

1 ≤ R ≤ 1,000

입력형식

첫 줄에 조직도의 높이 H, 말단에 대기하는 업무의 개수 K, 업무가 진행되는 날짜 수 R이 주어진다.

그 다음 줄부터 각각의 말단 직원에 대해 대기하는 업무가 순서대로 주어진다.

제일 왼쪽의 말단 직원부터 순서대로 주어진다.

출력형식

완료된 업무들의 번호 합을 정수로 출력한다.

입력예제1

1 1 1 1 2

출력예제1

0

 

입력예제2

1 3 2 9 3 7 5 11 2

출력예제2

5

 

 

 

 

핵심 설명

쉽게 생각하자 쉽게.

- 큰 개념은 홀수일에는 왼쪽 자식이 준 업무만 처리할 수 있고, 짝수일에는 오른쪽 자식이 준 업무만 처리할 수 있다.

- 말단노드 큐에 업무를 싹 넣어준다. (일감을 쌓아준다!)

- 업무를 처리하는것을 Queue.remove() 라고 보면 된다.

- 위 메소드로 꺼내온 값은 상사에게 넘겨주는데, 본인이 왼쪽자식인지 오른쪽자식인지를 구분해서 넘겨줘야 한다.

- 부서장(루트)이면 합계변수에 더해준다.

 

업무일수만 바꿔가며 테스트 케이스를 넣어보았다

1 3 2
9 3 7
5 11 2
// 정답 5

 

문제의 테스트케이스에서 업무일수만 3으로 바꾸면 5+9 = 14라는 정답이 나올것이다.

1 3 3
9 3 7
5 11 2
// 정답 14

 

 

 

 

 

 

 

전체코드

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

public class Main {

    public static long dap = 0;

    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());
        int h = Integer.parseInt(st.nextToken());   // 조직도높이
        int k = Integer.parseInt(st.nextToken());   // 말단대기업무개수
        int r = Integer.parseInt(st.nextToken());   // 업무진행날짜

        int totalNodeCount = (1<<h+1) - 1;  // 전체노드개수 (h=2일때 2^3-1 = 7개)
        int leafNodeCount = (1<<h);         // 말단노드개수 (h=2일때 2^2 = 4개)
        // System.out.println(totalNodeCount + " " + leafNodeCount);

        // 전체노드개수만큼 큐 생성(좌측 우측 나눠서)
        Queue<Integer>[][] q = new Queue[totalNodeCount][2];
        for(int i=0; i<q.length; i++){
            for(int j=0; j<q[0].length; j++){
                q[i][j] = new LinkedList<Integer>();
            }
        }

        // 제일 왼쪽 말단노드부터 ~제일 오른쪽 말단노드까지 돌면서 (h=2일때 인덱스는 3,4,5,6 돌면서)
        for(int i=totalNodeCount-leafNodeCount; i<totalNodeCount; i++){
            // System.out.println("i : " + i);
            // 말단대기업무개수 전부 넣어주기
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<k; j++){
                q[i][0].add(Integer.parseInt(st.nextToken()));  // 말단직원은 무조건 왼쪽에 넣어주기..!
            }
        }
        // 세팅 끝


        // ##### 일 시작 #####
        dap = 0;
        // 1일~r일간, 부서장/팀원/막내 분기처리해서 일 시킬건데
        for(int day=1; day<=r; day++){

            // 전체 노드를 돌면서 전직원 일시킬건데
            for(int i=0; i<totalNodeCount; i++){

                // System.out.println("["+day+"]"+" i: " + i + ", left/right = " + q[i][0].peek() + " " + q[i][1].peek());

                // 부서장이면, 홀수일엔 왼쪽 일을, 짝수일에는 오른쪽 일을, 처리해서 완료한다.
                if(i == 0){
                    if(day%2 == 1){     // 홀수일이니 왼쪽 부하 직원이 올린 업무만 처리해주자
                        if(!q[i][0].isEmpty()) {     // 왼쪽 부하 직원이 올린 일감이 있으면
                            int leftWork = q[i][0].remove();
                            dap += leftWork;         // 완료처리
                            // System.out.println("dap += " + leftWork);
                        }
                    }else{              // 짝수일이니 오른쪽 부하 직원이 올린 업무만 처리해주자
                        if(!q[i][1].isEmpty()) {
                            int rightWork = q[i][1].remove();
                            dap += rightWork;
                            // System.out.println("dap += " + rightWork);
                        }
                    }
                }
                // 중간 팀원이면
                else if( 0 < i && i < totalNodeCount-leafNodeCount){
                    int parent = (i-1)/2;           // 부모인덱스 찾아놓고
                    if(day%2 == 1) {                // 홀수일이니 왼쪽 부하 직원이 올린 업무만 처리해주자
                        if(!q[i][0].isEmpty()) {    // 왼쪽 부하 직원이 올린 일감이 있으면
                            int leftChildWork = q[i][0].remove();
                            if(i%2 == 1){               // 저는 왼쪽 자식입니다 홀수일에 처리하실 업무 드려요~ 하고 [0]에 넣어주기
                                q[parent][0].add(leftChildWork);
                            }else{                      // 저는 오른쪽 자식입니다 짝수일에 처리하실 업무 드려요~ 하고 [1]에 넣어주기
                                q[parent][1].add(leftChildWork);
                            }
                        }
                    }
                    else{                           // 짝수일이니 오른쪽 부하 직원이 올린 업무만 처리해주자
                        if(!q[i][1].isEmpty()) {
                            int rightChildWork = q[i][1].remove();
                            if(i%2 == 1){               // 저는 왼쪽 자식입니다 홀수일에 처리하실 업무 드려요~ 하고 [0]에 넣어주기
                                q[parent][0].add(rightChildWork);
                            }else{                      // 저는 오른쪽 자식입니다 짝수일에 처리하실 업무 드려요~ 하고 [1]에 넣어주기
                                q[parent][1].add(rightChildWork);
                            }
                        }
                    }
                }
                // 막내면
                else{
                    int parent = (i-1)/2;           // 부모인덱스 찾아놓고

                    // 꺼내오는건 날짜 상관없이 [i][0]이 비어있지 않으면 상사한테 넣어주기
                    if(!q[i][0].isEmpty()) {        // 말단은 무조건 왼쪽 [i][0] 에서 꺼내옴
                        int leafWork = q[i][0].remove();
                        if(i%2 == 1){               // 저는 왼쪽 자식입니다 홀수일에 처리하실 업무 드려요~ 하고 [0]에 넣어주기
                            q[parent][0].add(leafWork);
                        }else{                      // 저는 오른쪽 자식입니다 짝수일에 처리하실 업무 드려요~ 하고 [1]에 넣어주기
                            q[parent][1].add(leafWork);
                        }
                    }
                }
            }
        }

        bw.write(String.valueOf(dap));
        bw.flush();
        bw.close();
        return;
    }

}